二叉树的最近公共祖先

视频讲解

晕递归的同学请先看深刻理解递归。

答疑

问： $lowestCommonAncestor$ 函数的返回值是什么意思？

答：返回值的准确含义是「最近公共祖先的候选项」。对于最外层的递归调用者来说，返回值是最近公共祖先的意思。但是，在递归过程中，返回值可能是最近公共祖先，也可能是空节点（表示子树内没找到任何有用信息）、节点 $p$ 或者节点 $q$ （可能成为最近公共祖先，或者用来辅助判断上面的某个节点是否为最近公共祖先）。

问：为什么发现当前节点是 $p$ 或者 $q$ 就不再往下递归了？万一下面有 $q$ 或者 $p$ 呢？

答：如果下面有 $q$ 或者 $p$ ，那么当前节点就是最近公共祖先，直接返回当前节点。如果下面没有，那既然都没有要找的节点了，也不需要递归，直接返回当前节点。（注意题目保证 $p$ 和 $q$ 都在二叉树中）

Python 解法1C++ 解法1

python

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root in (None, p, q):  # 找到 p 或 q 就不往下递归了，原因见上面答疑
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left and right:  # 左右都找到
            return root  # 当前节点是最近公共祖先
        # 如果只有左子树找到，就返回左子树的返回值
        # 如果只有右子树找到，就返回右子树的返回值
        # 如果左右子树都没有找到，就返回 None（注意此时 right = None）
        return left or right

cpp

// C++ 版待补充

C++ 解法2

cpp

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr || root == p || root == q) {
            return root; // 找到 p 或 q 就不往下递归了，原因见上面答疑
        }
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if (left && right) { // 左右都找到
            return root; // 当前节点是最近公共祖先
        }
        // 如果只有左子树找到，就返回左子树的返回值
        // 如果只有右子树找到，就返回右子树的返回值
        // 如果左右子树都没有找到，就返回 nullptr（注意此时 right = nullptr）
        return left ? left : right;
    }
};

复杂度分析

时间复杂度： $O (n)$ ，其中 $n$ 为二叉树的节点个数。
空间复杂度： $O (n)$ 。最坏情况下，二叉树是一条链，因此递归需要 $O (n)$ 的栈空间。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

视频讲解 ​

答疑 ​

复杂度分析 ​

分类题单 ​

视频讲解

答疑

复杂度分析

分类题单