这段代码使用什么算法来找到二叉树的最低共同祖先?

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，则返回它。

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

然后是最后 3 个if。

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。