0236. 二叉树的最近公共祖先 #

标签：树
难度：中等

题目大意 #

描述：给定一个二叉树的根节点 root，以及二叉树中两个节点 p 和 q。

要求：找到该二叉树中指定节点 p、q 的最近公共祖先。

说明：

祖先：如果节点 p 在节点 node 的左子树或右子树中，或者 p == node，则称 node 是 p 的祖先。
最近公共祖先：对于树的两个节点 p、q，最近公共祖先表示为一个节点 lca_node，满足 lca_node 是 p、q 的祖先且 lca_node 的深度尽可能大（一个节点也可以是自己的祖先）。
树中节点数目在范围 $[2, 10^5]$ 内。
$-10^9 \le Node.val \le 10^9$。
所有 Node.val 互不相同。
p != q。
p 和 q 均存在于给定的二叉树中。

示例：

示例 1：

1
2
3


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

示例 2：

1
2
3


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

解题思路 #

思路 1：递归遍历 #

设 lca_node 为节点 p、q 的最近公共祖先。则 lca_node 只能是下面几种情况：

p、q 在 lca_node 的子树中，且分别在 lca_node 的两侧子树中。
p == lca_node，且 q 在 lca_node 的左子树或右子树中。
q == lca_node，且 p 在 lca_node 的左子树或右子树中。

下面递归求解 lca_node。递归需要满足以下条件：

如果 p、q 都不为空，则返回 p、q 的公共祖先。
如果 p、q 只有一个存在，则返回存在的一个。
如果 p、q 都不存在，则返回 None。

具体思路为：

如果当前节点 node 等于 p 或者 q，那么 node 就是 p、q 的最近公共祖先，直接返回 node。
如果当前节点 node 不为 None，则递归遍历左子树、右子树，并判断左右子树结果。
1. 如果左右子树都不为空，则说明 p、q 在当前根节点的两侧，当前根节点就是他们的最近公共祖先。
2. 如果左子树为空，则返回右子树。
3. 如果右子树为空，则返回左子树。
4. 如果左右子树都为空，则返回 None。
如果当前节点 node 为 None，则说明 p、q 不在 node 的子树中，不可能为公共祖先，直接返回 None。

思路 1：代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root == p or root == q:
            return root

        if root:
            node_left = self.lowestCommonAncestor(root.left, p, q)
            node_right = self.lowestCommonAncestor(root.right, p, q)
            if node_left and node_right:
                return root
            elif not node_left:
                return node_right
            else:
                return node_left
        return None

思路 1：复杂度分析 #

时间复杂度：$O(n)$。其中 $n$ 是二叉树的节点数目。
空间复杂度：$O(n)$。