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

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

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

思路

基本思想

为了找到两个节点的最近公共祖先,需要选择一个遍历方式,此处选择后序遍历,这是因为后序遍历的遍历顺序为左右根,也就是自底向上遍历,这样遇到的第一个祖先就是最近的公共祖先

最近公共祖先的状态右两种:

1. p和q分别位于这个公共祖先两边,此时这个节点就是公共祖先
2. p或者q就是另外一个节点的祖先,此时p或者q就是公共祖先

相当于要么位于两侧,要么位于一条路径上,第一种情况在图中就是假设p是6,q是2,此时5

就是最近的公共祖先,第二种情况在图中就是假设p为5,q为6,那么p就是最近的公共祖先

此时后序遍历一旦遇到p或者q亦或者空,就立即返回,向上返回时,一旦某个节点的左或者右有返回值,说明遇到了p或者q亦或者空,当返回值不为空时需要进行判断将其分成两种情况:

1. 左右都不为空,由于是后序遍历,此时说明当前节点就是遇到的最近的公共祖先,直接返回当前节点
2. 左右有一个为空,此时说明不为空的一边遇到了p或者q,此时直接返回原值,也就是不为空的返回值

总结起来就是一旦遇到了p或者q就提前返回,一层一层向上,到了根节点就会退出遍历,此时记录的值就是最近的公共祖先

拿图中举例,假设p是6,q是4,此时后序遍历先遍历左边,一路向下遇到了p,也就是6,此时就提前结束左边的遍历,向上返回,返回到5时,左侧不为空,右侧向下遍历遇到q时一层一层向上返回原值,直到5这个节点,此时由于左右都不为空,向上返回5,到了根节点结束遍历,返回最终的结果5

执行流程

1. 正常的后序遍历

2. 在遇到空返回的条件上加上遇到p或者q也返回

3. 一旦当前节点的左或者右不为空,此时分为两种情况

   1. 只有一侧不为空,原值向上返回
   2. 两侧都不为空,返回当前节点

4. 到了根节点退出遍历,返回最终的结果

代码

根据以上分析,得出以下代码:

 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;
       	//在这里返回原值
        return left!=nullptr?left:right;
    }
};

总结

遇到p或者q就会一层一层向上返回原值,直到某个节点的左右两侧都不为空,此时返回当前节点,再向上还是返回原值,最终一层一层向上,到了根节点退出遍历,返回最终的结果,就是最近的公共祖先