（转载）二叉树，给定任何两个节点，求两个节点的最小公共节点(JAVA 代码实现)
* 类型与 这样的一个二叉树
* 3
* / \
* 5 1
* / \ / \
* 6 2 0 8
* / \
* 7 4
* 当 给定 4 0 的时候 返回 3
* 当 给定 7 4 的时候 返回 2
* 当 给定 3 8 的时候 返回 3
给定的俩个 节点 会有以下情况：
1: 给定的俩个 节点 有一个是根节点 或者 俩个是根节点 ，那么返回就是 根节点 3
2: 给定的俩个 节点 俩个都不是根节点
1: 都在左侧 (使用递归时，二叉树右节点是找不到相对应的父节点的)
2: 都在右侧 (使用递归时，二叉树左节点是找不到相对应的父节点的)
3: 在俩侧
思路：设定给的俩个节点为 p,q, 选择使用递归,递归该二叉树的所有节点。
传入当前节点，当前节点等于null. 直接返回，这时表示已经递归到最深的节点了（比如说传入的是 6 的子节点）.或者是 传入的当前节点等于 p,q的值. 表示已经找到该节点，需要返回，再根据该节点去找父节点.
方法代码：
/*** 类型与 这样的一个二叉树* 3* / \* 5 1* / \ / \* 6 2 0 8* / \* 7 4* 当 给定 4 0 的时候 返回 3* 当 给定 7 4 的时候 返回 2* 当 给定 3 8 的时候 返回 3* @param root* @param p* @param q* @return*/private static TreeNode getCommentLatestNode(TreeNode root, TreeNode p, TreeNode q) {if (root == null || p.getValue().equals(root.getValue()) || q.getValue().equals(root.getValue())) {return root;}TreeNode left = getCommentLatestNode(root.getLeft(), p, q);TreeNode right = getCommentLatestNode(root.getRight(), p, q);// 没有找到元素if (left == null && right == null) {return null;// 都在右侧} else if (left == null) {return right;// 都在左侧} else if (right == null) {return left;}// 在俩侧return root;}
TreeNode 代码：
public class TreeNode {private Integer value;/*** 跟节点*/private TreeNode root;/*** 左孩子节点*/private TreeNode left;/*** 右孩子节点*/private TreeNode right;public TreeNode() {}public TreeNode(Integer value) {this.value = value;}/*** 增加节点*/public void addTreeNode( int nodeValue){// 第一次添加if (root == null) {root = new TreeNode(nodeValue);return;}if (this.root.value.compareTo(nodeValue) > 0) {addTreeNode(root, root.left, nodeValue, true);}addTreeNode(root, root.right, nodeValue, false);}private void addTreeNode(TreeNode rootNode, TreeNode node, int nodeValue, boolean left) {if (node == null) {if (left) {rootNode.left = new TreeNode(nodeValue);} else {rootNode.right = new TreeNode(nodeValue);}return;}if (node.value.compareTo(nodeValue) >= 0) {addTreeNode(node, node.left, nodeValue, true);}addTreeNode(node, node.right, nodeValue, false);}public TreeNode getRoot(){return root;}public Integer getValue() {return value;}public TreeNode getLeft() {return left;}public TreeNode getRight() {return right;}}
测试全部代码:
public class RecentNode {public static void main(String[] args) {TreeNode root = getTrade();TreeNode node = getCommentLatestNode(root, new TreeNode(3), new TreeNode(8));System.out.println("args = " + (node == null ? "未找到相应节点" : node.getValue()));}
/*** 类型与 这样的一个二叉树* 3* / \* 5 1* / \ / \* 6 2 0 8* / \* 7 4* 当 给定 4 0 的时候 返回 3* 当 给定 7 4 的时候 返回 2* 当 给定 3 8 的时候 返回 3* @param root* @param p* @param q* @return*/private static TreeNode getCommentLatestNode(TreeNode root, TreeNode p, TreeNode q) {if (root == null || p.getValue().equals(root.getValue()) || q.getValue().equals(root.getValue())) {return root;}TreeNode left = getCommentLatestNode(root.getLeft(), p, q);TreeNode right = getCommentLatestNode(root.getRight(), p, q);// 没有找到元素if (left == null && right == null) {return null;// 都在右侧} else if (left == null) {return right;// 都在左侧} else if (right == null) {return left;}// 在俩侧return root;}/*** 构建 treeNode* @return*/private static TreeNode getTrade() {TreeNode treeNode = new TreeNode();int[] nodes = {3,5,1,6,2,0,8,7,4};Arrays.stream(nodes).forEach(e ->{treeNode.addTreeNode(e);});return treeNode.getRoot();}}