236. 二叉树的最近公共祖先 Medium

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1:
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2:
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3:
输入：root = [1,2], p = 1, q = 2
输出：1

解题思路

输入：二叉树的根节点 root，以及两个指定节点 p 和 q

输出：返回这两个节点的最低公共祖先

本题适合使用自底向上的 DFS 解决。

我们可以归纳出以下 3 种情况：

1. 如果 p 和 q 分别位于当前节点的左右子树中，则当前节点为最低公共祖先。
2. 如果 p 和 q 都在左子树中，则最低公共祖先是左子树中先找到的节点。
3. 如果 p 和 q 都在右子树中，则最低公共祖先是右子树中先找到的节点。

因此，我们通过 DFS 遍历节点，寻找 p 或 q。找到任一节点后返回该节点，然后根据左右子树的返回值判断最低公共祖先并向上返回。

分类讨论
│
├── 当前节点为空
│   └── 返回空节点（None）
│
├── 当前节点是 p
│   └── 返回当前节点（p）
│
├── 当前节点是 q
│   └── 返回当前节点（q）
│
└── 其他情况（递归左右子树）
    │
    ├── 左右子树都找到
    │   └── 返回当前节点（最近公共祖先）
    │
    ├── 只有左子树找到
    │   └── 返回左子树的结果
    │
    ├── 只有右子树找到
    │   └── 返回右子树的结果
    │
    └── 左右子树都没有找到
        └── 返回空节点（None）

代码实现

python

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        """
        寻找二叉树中两个节点的最近公共祖先（LCA）
        思路：后序遍历（自底向上），先递归左右子树，再处理当前节点
        """
        # 如果当前节点为空，或者当前节点就是 p 或 q，则直接返回当前节点
        if root is None or root == p or root == q:
            return root
        
        # 在左子树中查找 p 和 q 的最近公共祖先
        left = self.lowestCommonAncestor(root.left, p, q)
        # 在右子树中查找 p 和 q 的最近公共祖先
        right = self.lowestCommonAncestor(root.right, p, q)

        # 如果左右子树都找到了 p 或 q，说明当前节点就是最近公共祖先
        if left and right:
            return root
        
        # 如果左子树找到，则返回左子树结果
        if left:
            return left
        
        # 如果右子树找到，则返回右子树结果
        return right

javascript

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    if (!root || root == p || root == q) return root;

    const left = lowestCommonAncestor(root.left, p, q);
    const right = lowestCommonAncestor(root.right, p, q);

    if (left && right) return root;

    if (left) return left;

    return right;
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(h)

链接

236 国际版

236 中文版