Q236-二叉树的最近公共祖先-中等-树

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

Question

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

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

Example 1:

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

Example 2:

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

Note:

树中节点数目在范围 [2, 105] 内。

-109 <= Node.val <= 109

所有 Node.val 互不相同。

p != q

p 和 q 均存在于给定的二叉树中。

Apporach 1: 直接递归方法

对每个结点的 left / right 两个子节点递归判断是否包含 p 和 q

当 left 和 right 同时为空：说明 root 的左 / 右子树中都不包含 p,q ，返回 null ；
当 left 和 right 同时不为空：说明 p, q 分列在 root 的异侧（分别在左 / 右子树），因此 root 为最近公共祖先，返回 root ；
当 left 为空，right 不为空：p,q 都不在 root 的左子树中，直接返回 right 。具体可分为两种情况：
- p,q 其中一个在 root 的右子树中，此时 right 指向 p（假设为 p ）；
- p,q 两节点都在 root 的右子树中，此时的 right 指向最近公共祖先节点；
当 left 不为空， right 为空：与情况 3. 同理；

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

复杂度分析

时间复杂度 O(N) ：其中 N 为二叉树节点数；最差情况下，需要递归遍历树的所有节点.
空间复杂度 O(N) ：最差情况下，递归深度达到 N，系统使用 O(N) 大小的额外空间。

Approach 2: 递归

我们递归遍历整棵二叉树，定义表示 x 节点的子树中是否包含 p 节点或 q 节点，如果包含为 true，否则为 false。那么符合条件的最近公共祖先 x 一定满足如下条件：

其中和分别代表 x 节点的左孩子和右孩子。初看可能会感觉条件判断有点复杂，我们来一条条看，说明左子树和右子树均包含 p 节点或 q 节点，如果左子树包含的是 p 节点，那么右子树只能包含 q 节点，反之亦然，因为 p 节点和 q 节点都是不同且唯一的节点，因此如果满足这个判断条件即可说明 x 就是我们要找的最近公共祖先。再来看第二条判断条件，这个判断条件即是考虑了 x 恰好是 p 节点或 q 节点且它的左子树或右子树有一个包含了另一个节点的情况，因此如果满足这个判断条件亦可说明 xx 就是我们要找的最近公共祖先。

你可能会疑惑这样找出来的公共祖先深度是否是最大的。其实是最大的，因为我们是自底向上从叶子节点开始更新的，所以在所有满足条件的公共祖先中一定是深度最大的祖先先被访问到，且由于本身的定义很巧妙，在找到最近公共祖先 x 以后，按定义被设置为 true ，即假定了这个子树中只有一个 p 节点或 q 节点，因此其他公共祖先不会再被判断为符合条件。

下图展示了一个示例，搜索树中两个节点 9 和 11 的最近公共祖先。

class Solution {
public:
    TreeNode* ans;
    bool dfs(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr) return false;
        bool lson = dfs(root->left, p, q);
        bool rson = dfs(root->right, p, q);
        if ((lson && rson) || ((root->val == p->val || root->val == q->val) && (lson || rson))) {
            ans = root;
        }
        return lson || rson || (root->val == p->val || root->val == q->val);
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        dfs(root, p, q);
        return ans;
    }
};

复杂度分析

时间复杂度：O(N)，其中 N 是二叉树的节点数。二叉树的所有节点有且只会被访问一次，因此时间复杂度为 O(N)。
空间复杂度：O(N) ，其中 N 是二叉树的节点数。递归调用的栈深度取决于二叉树的高度，二叉树最坏情况下为一条链，此时高度为 N，因此空间复杂度为 O(N)。