题目地址：

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

寻找一棵二叉树某两个节点$p$p和$q$q的最近公共祖先。

先证：$w$w是$p$p与$q$q的最近公共祖先，当且仅当$w=p$w=p且$q$q是$p$p的后代（或者反之），或者$p$p与$q$q分别在$w$w的左右子树之中。

先证充分性：若$p$p与$q$q分别位于$w$w的左右子树中，那么很显然$w$w是公共祖先，并且$w$w的左右子树根都不是公共祖先，这说明了$w$w的“最近”性质。证毕。

再证必要性：反证法。不妨设$p$p与$q$q都位于$w$w的左子树中，那么$w$w的左子树根是更近的公共祖先，与$w$w的“最近”性质矛盾。证毕。

所以只需要找到一个$p$p和$q$q分别位于它左右子树的那个节点就行了。为此我们需要在root的左右两个子树中搜索$p$p和$q$q，如果一边搜索出$p$p另一边搜索出$q$q返回即可。代码如下：

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        
        if (left != null && right != null) {
            return root;
        } else if (left == null) {
            return right;
        } else {
            return left;
        }
    }
}

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) {
        val = x;
    }
}

时间复杂度$O(n)$O(n)，空间$O(h)$O(h)。

算法正确性证明：

需要证明这个函数，若以root为树根的树中存在$p$p与$q$q，则会返回其最近公共祖先，若只存在$p$p或$q$q，则对应地返回$p$p或$q$q，否则会返回null。
如果root是$p$p或者$q$q显然正确。如果树的节点数为$0$0，$1$1，$2$2或$3$3时显然正确；假设树的节点数是$k$k的时候也正确，如果树的节点数是$k+1$k+1，那么其左右子树节点数必然小于等于$k$k，据数学归纳法，若left与right里分别有$p$p和$q$q，那说明$p$p和$q$q在root的两端，那就返回root。否则按照数学归纳法，就返回了正确答案。证毕。

• 点赞
• 收藏
• 分享
• • 文章举报

edWard的算法世界 发布了140 篇原创文章 · 获赞 0 · 访问量 7773 私信 关注