（转载）二叉树，给定任何两个节点，求两个节点的最小公共节点(JAVA 代码实现)

vlambda
2021-07-12

（转载）二叉树，给定任何两个节点，求两个节点的最小公共节点(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(); }}