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

题目

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

百度百科中最近公共祖先的定义为：“对于有根树 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

提示：

• 树中节点数目在范围 [2, 10^5] 内。
• -10^9 <= Node.val <= 10^9
• 所有 Node.val 互不相同 。
• p != q
• p 和 q 均存在于给定的二叉树中。

解答

思路

分类讨论当前遍历的节点是什么：我们从一整棵树的根节点出发，如果根节点是：

• 空节点：返回空
• p 节点：p 为根，说明 q 在它的下面，返回当前节点即可（有人可能会说，q 不一定在它下面啊，注意：我们这里是从一整棵树的根节点出发的，也就是说我并不关心其他子树是什么情况，只是就当前这棵树而言，假设 p, q 都在其中，而 p 恰好为根节点，那么祖先一定是 p）
• q 节点：同理返回当前节点

更多的情况是其他节点，此时递归搜索左右子树：

• 左右子树都找到：返回当前节点，因为恰好它的左右子树分别存在 p, q，它就是 公共祖先
• 只有左子树找到：返回递归左子树的结果（可能是 LCA，也可能只是 p, q，总之有结果）
• 只有右子树找到：返回递归右子树的结果
• 左右子树都没找到：返回空节点

注意：所谓 找到 就是上述找到 p, q 的过程。这又是一个 后序遍历 的过程（先遍历左右子树，再根据返回值更新根节点的值）。

代码

Python 代码

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

        if left and right:
            return root # LCA
        
        if left:
            return left
        return right