此代码使用什么算法来查找二叉树的最低公共祖先？

Question

我在尝试解决这个问题时在 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;
}

Answer 1

很简单：

代码查看树的根。如果根是p或q，那么就returns吧。

如果不在根中，则在根的左右子树中查找，重复这个过程，直到root实际上是p或q。

然后是最后 if 的 3 个。

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。