2021/05/05
看似正确的 LCA
这个解法对 lowestCommonAncestor 定义为：
- 如果 p 和 q 都在 树中，返回 p 和 q 的最近公共祖先。
- 否则返回 p 或者 q（当 p 和 q 均不在树中时，才返回 null）。
该解法只有在 p 和 q 都是树中存在的结点时，才会返回 LCA。
如果 p 在树中，q 不在树中，会返回 p，并不符合 LCA 的预期。
强调一下递归的子问题的返回结果是什么：
- 返回的是LCA
- 是其中一个结点
- null（1 和 2 都没找到）
如果 p 刚好是 q 的祖先，这个算法自始至终都没有找到过 q（q 被 p 挡住了），算法找到了 p 就返回了，此时刚好 p 就是 p 和 q 的 LCA。
已通过本地 DEBUG 验证了上述分析。
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) return root;
TreeNode l = lowestCommonAncestor(root.left, p, q);
TreeNode r = lowestCommonAncestor(root.right, p, q);
if (l == null && r == null) return null; // 这一行可以去掉，左边和右边都没找到 p/q
if (r == null) return l;
if (l == null) return r;
return root; // 左边和右边分别找到了 p 和 q
}
}
正确的 LCA
这个算法才是能返回正确结果的 LCA，递归的 containsPorQ 的返回是，树下面是否包含 p 结点或 q 结点。
子问题 l 是左子树是否包含了 p 或 q
子问题 r 是右子树是否包含了 p 或 q
- 当
l && r为真时，表示左右子树分别包含了 p 和 q 的其中一个，那么当前节点就是 p 和 q 的最小公共祖先。 - 当
(root == p || root == q) && (l || r)为真时，表示后序遍历时发现了当前结点就是 p 或 q 了，此时如果当前结点的子树中也存在 q 或者 p，那么当前节点就是 p 和 q 的最小公共祖先。
class Solution {
private TreeNode ans = null;
public boolean containsPorQ(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return false;
boolean l = containsPorQ(root.left, p, q);
boolean r = containsPorQ(root.right, p, q);
// 左边和右边分别找到了 p 和 q
if (l && r) {
ans = root;
return true;
}
// root 就是 p 或 q，并且 root 的子树也找到了 q 或 p
if ((root == p || root == q) && (l || r)) {
ans = root;
return true;
}
// 返回 root 下面到底有没有 p 或 q
return l || r || root == p || root == q;
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
containsPorQ(root, p, q);
return ans;
}
}