二叉树的最近公共祖先

难度: Easy

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

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

例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

示例 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。因为根据定义最近公共祖先节点可以为节点本身。

说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。

注意：本题与主站 236 题相同：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/

Submission

运行时间: 88 ms

内存: 25.6 MB

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        if root is None or p == root or q == root:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if right is None and left is None:
            return None
        elif right is None:
            return left
        elif left is None:
            return right
        return root

Explain

该题解采用递归的方式查找二叉树中两个节点的最近公共祖先。首先，递归函数检查当前节点是否为null，或者等于p或q中的任何一个，如果是，则返回当前节点，因为找到了p或q节点之一，或者已经到达了树的底部。然后，函数递归地在左子树和右子树中分别寻找p和q。根据左右子树的返回值，可以判断出：1) 如果左子树和右子树均返回null，则当前子树不包含p或q，返回null。2) 如果只有一边子树返回了非null（说明该子树找到了p或q），则返回该非null值。3) 如果左右两边均返回非null值，说明当前节点正好是p和q的分叉点，即最近公共祖先，因此返回当前节点。

时间复杂度: O(n)

空间复杂度: O(n)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        # 如果到达叶子节点的下一层，或找到p或q，则返回root
        if root is None or p == root or q == root:
            return root
        # 在左子树中查找p和q
        left = self.lowestCommonAncestor(root.left, p, q)
        # 在右子树中查找p和q
        right = self.lowestCommonAncestor(root.right, p, q)
        # 如果左右子树的返回都是None，说明这两个节点在当前子树中都未找到
        if right is None and left is None:
            return None
        # 如果右子树是None，说明两个节点都在左子树
        elif right is None:
            return left
        # 如果左子树是None，说明两个节点都在右子树
        elif left is None:
            return right
        # 如果左右子树都不是None，说明当前节点是p和q的最近公共祖先
        return root

Explore

即使当前节点不是null、p或q，我们还需要继续在其左右子树中递归查找，因为p和q可能位于当前节点的下层。递归查找的目的是在整个树中定位p和q的位置，并确认它们的最近公共祖先。如果我们停止在当前节点递归，那么我们可能会错过包含p或q的路径，因此无法正确判断或找到其最近公共祖先。

如果p和q分别位于根节点的两侧，递归函数会在左子树中找到p（或q），并在右子树中找到q（或p）。在这种情况下，左子树和右子树的递归调用将分别返回非null值，指示找到了p和q。根据算法逻辑，当左右子树调用都返回非null（一个返回p，另一个返回q），当前根节点将被确认为p和q的最近公共祖先。因此，递归函数会返回当前根节点作为结果。

如果p是q的父节点或祖先（或反之），则递归查找将在遇到p或q时首先返回该节点。例如，如果p是q的父节点，当递归到达p时，它会返回p，因为p已经是q的父节点。由于递归的下一步是在p的子树中查找q，它将在p的子树中找到q，最终返回p作为最近公共祖先。因此，当其中一个节点是另一个的祖先时，该祖先节点会被返回为最近公共祖先。