0

在尝试解决这个问题时，我在 Leetcode 上找到了这个解决方案：

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/

Leetcode 上的每个人似乎都理所当然地认为这是如何工作的。但我不明白。这里发生了什么，这是使用什么算法来查找二叉树的 LCA？

public TreeNode lowestCommonAncestorBinaryTree(TreeNode root, TreeNode p, TreeNode q) {
    if(root==null) {
        return null;
    }
    if(root==p) {
        return p;
    }
    if(root==q) {
        return q;
    }
    TreeNode left = lowestCommonAncestorBinaryTree(root.left, p, q);
    TreeNode right = lowestCommonAncestorBinaryTree(root.right, p, q);
    if (left != null && right != null) {
        return root;
    }
    if(left!=null && right==null) {
        return left;
    }
    if(right!=null && left==null) {
        return right;
    }
    return null;
}
4

1 回答 1

1

非常简单：

代码查看树的根。如果根是por q，则返回它。

如果不在根中，则在根的左右子树中搜索，重复该过程直到root实际为p或q。

然后是最后 3 个ifs。

  1. if (left != null && right != null) return root;

    这意味着它在根的左子树中找到了一个节点，在根的右子树中找到了另一个节点，因此根是 LCA。

  2. if(left != null && right == null) return left;

    这意味着它在左子树中找到了一个节点，但在右子树中没有节点，那么左节点是另一个节点的父节点，因此是 LCA。

  3. if(right != null && left == null) return right;

    这意味着它在右子树中找到了一个节点，但在左子树中没有节点，则右节点是另一个节点的父节点，因此是 LCA。

否则，节点不在树中并且没有 LCA。

于 2020-01-25T22:08:55.083 回答