🦧 236.二叉树的公共祖先

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

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

思路

基本思想

为了求两个节点的公共祖先，手工求解直接自底向上，遇到第一个交叉的节点就是两个节点的公共祖先，代码中为了模拟这种自底向上的流程，需要使用后序遍历

公共祖先出现的位置一共有三种情况：

1. 二叉树为空，没有公共祖先
2. 公共祖先是p或者q
3. 公共祖先不是p也不是q

所以在后序遍历的过程中，遇到了p或者q，可以直接返回

也就是当前节点如果是p或者q亦或者是nullptr，则直接返回当前节点

然后在左右子树中搜索公共祖先，此时右两种情况：

1. 左右子树都不为空，代表左右子树中遇到了p和q，相当于当前节点就是p和q的公共祖先

   也就是p和q分布在当前节点的左右子树中，因为左右子树中遇到饿了p和q才会返回不为空的结果

2. 左右子树任有一个为空，此时说明p或者q就是当前节点的公共祖先，因为左右子树遇到p或者q亦或者nullptr才会返回，如果任有一个为空，说明p和q都出现在当前节点的一侧，此时只需要返回p或者q即可

当遍历的过程中遇到了p或者q亦或者nullptr时，提前结束后序遍历

执行流程

1. 后序遍历二叉树

2. 遇到p或者q亦或者nullptr就返回

3. 当前节点的左右子树返回值都不为空，说明q和p出现在当前节点的两侧，返回当前节点作为公共祖先

   

4. 当前节点的左右子树返回值有一个为空，说明p和q出现在当前节点的一侧，返回p或者q作为两个节点的公共祖先

   

代码

根据以上分析，得出以下代码：

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

class Solution {
public:
    //一旦找到
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        //当前节点为空节点或者遇到了p或者q，提前结束吧后序遍历
        if(root==nullptr||root==p||root==q)
            return root;
        //正常后序遍历
        TreeNode* left=lowestCommonAncestor(root->left,p,q);
        TreeNode* right=lowestCommonAncestor(root->right,p,q);
        //p和q出现在当前节点的两侧，当前节点就是公共祖先
        if(left!=nullptr&&right!=nullptr)
            return root;
        //p和q出现在当前节点的一侧
        return left!=nullptr?left:right;
    }
};

总结

采用后序遍历求公共祖先，p和q出现在当前节点的两侧，说明当前节点就是公共祖先，p和q出现在当前节点的一侧，说明p和q其中一个为公共祖先，此时先遇到谁谁就是公共祖先