剑指 Offer 68 – II. 二叉树的最近公共祖先

题目描述

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 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/

解题思路

后续遍历的特点为，子节点的状态可以通过递归的方式传给父节点。本题目适合使用后续遍历+递归的方式。
当某个点的左子树传回来的状态为“找到了符合的节点”，同时右子树传回来的状态也是“找到了符合的节点”。在这里，状态如果为null，说明没找到；如果是p或q，则返回这个p或q节点。
因此，当后序遍历时发现某个节点的两个状态都不为null，说明这个节点就是公共祖先节点。
最初的终止条件怎么确定呢？
- 如果遍历到了null，返回null
- 如果遍历到了p或者q，返回这个node
每次递归函数的返回值怎么根据左右子节点的返回值确定呢？
- 如果左右子节点都返回null（叶子结点或者是子树没货），返回null
- 如果左右子节点里面一个返回null，一个不是，则返回那个不是的node
- 如果左右节点都不返回null，这个点就是想找的最近公共祖先

解题代码

class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        if root is None:
            return None
        if root is p or root is q:
            return root
        l = self.lowestCommonAncestor(root.left, p, q)
        r = self.lowestCommonAncestor(root.right, p, q)
        if l is None and r is None:
            return None # 左右子树都没有p或q
        elif l is None and r is not None:
            return r # 即使是已经找到了最近公共祖先，也会因为l为none一直把状态返回到真正的root
        elif l is not None and r is None:
            return l # 即使是已经找到了最近公共祖先，也会因为r为none一直把状态返回到真正的root
        elif l is not None and r is not None:
            return root # 满足这个条件的节点是最近公共祖先

执行结果

执行结果：通过
执行用时：76 ms, 在所有 Python3 提交中击败了83.12%的用户
内存消耗：25.5 MB, 在所有 Python3 提交中击败了84.12%的用户