二叉树的最近公共祖先
文章目录
-
- 一、题目描述
- 二、解题思路
- 三、代码解析
一、题目描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。
以上面这个图为例子：
5和1 的最近公共祖先就是3。
二、解题思路
刚看到这个题，肯定会有点懵，我开始也很懵，根本不知道从何下手，没关系，只需要先将这个思路理解了，先将这个方法掌握啦，掌握的方法多了，慢慢就有了自己的思路了。
用什么遍历序列？
这题要问的是给定p,q的最近公共祖先。很明显，是找指定孩子结点的祖先结点。
那么，我们是不是应该先检查子孙，通过检查子孙返回的结果来判断当前结点是否是目标结点。
比如上面的例子，最后返回的是3，这个3是我们在检查完5和1后，发现5和1满足条件才认定3是最终结果的。
那么请问大家，用哪个遍历顺序？
A:中左右
B:左中右
C:左右中
答案明显是：C
根据遍历左右子树的结果来判断当前结点是不是要求的结点。
怎么用后序遍历解决这个问题？
首先考虑，我们对于每一个结点的左右子树应该返回什么内容，才能让判断这个结点是否是最近公共祖先？
还是刚才的例子，
我们发现3->left是5满足给定的p=5
我们发现3->right是1满足给定的q=1
所以，我们认为3是5,1的公共祖先。
那如果要求
p = 6
,
q = 1
的最近公共祖先呢？
明显能看出来，6和1的最近公共祖先还是3。
那是怎么判断的呢？
递归遍历3的左子树，如果左子树出现目标p或者q，就p或者q一层层返回上来。
遍历5的时候，如果5的左子树或者右子树出现p或者q，就返回上来。
总之：
无论在这个树的哪个位置找到了p或者q都要能把p,q返回到上一层，方便上层结点做判断。
所以说，递归函数返回值，返回的就是这个子树中是否有p,或者q。
如果有p或者q,就返回p或者q,如果没有就返回
。NULL
怎么通过左右子树返回的值判断最终的结果呢?
左右子树返会值会出现那些情况，有那些值是我们要返回的?
首先，如果遇到p,q肯定要返回。
其次，如果找到了【最近公共祖先】肯定也要返回
再次，如果不是上面两种情况，返回NULL就行了。
三、代码解析
看了上面的解析，可能还有点懵，那下面再结合具体代码理解
template<class T>
TreeNode<T>* lowestCommonAncestor(TreeNode<T>* root, TreeNode<T>* p, TreeNode<T>* q) {
//思路
/*
题目给了两个二叉树结点的指针，要返回这两个指针的最近的公共祖先。
首先，这个题只能使用后序遍历，左右中。因为后序是先访问两个叶子，再访问中间结点。
那根据后序遍历的访问顺序怎么操作呢？
我们将后序每个结点后序左右子树遍历的结果保存在left和right中。
如果有p那left保存的就是p
(只要左子树出现p就，整个左子树返回的就是p，q同理，右子树同理，如果p,q都没有出现，就返回NULL)
这样，对每一个结点都可以得到这个结点左右子树返回来的值。
我们就根据这个结点左右子树返回来的值来判断这个结点是不是p，q的最近公共结点。
怎么判断呢？左右子树可能跟返回如下三个值：p, q, NULL
那么请问，一个结点的左右子树满足那种情况的时候，这个结点是p, q的最近公共祖先呢？
当然只有两种情况：left:q, right:p 和left:p, right:q这两种情况了。
所以，这时候只需要做判断，如果左右子树返回的都不是NULL那么，当前处理的这个结点就是p,q的最近公共祖先了。
结束。
*/
//1.返回值和参数：返回值仍然是Treenode
//2.递归终止的条件
/*什么时候递归终止？
2.1 当前访问的结点是p或者q
2.2 当前访问到了空节点NULL(这个树是空树，或者叶子结点的孩子)
*/
if (root == q || root == p || root == NULL) return root;//对叶子结点的处理
//3.单层递归处理逻辑
//3.1 后序遍历左子树
TreeNode<T>* left = lowestCommonAncestor(root->left, p, q);
//3.2 后序遍历右子树
TreeNode<T>* right = lowestCommonAncestor(root->right, p, q);
//3.3 后序遍历处理中间结点
//问题：这里为什么判断的是左右子树返回值不为NULL，为什么不判断左右子树返回值是p,q?
/*
因为，我们要向上传递的是四种值：NULL,p,q,最近公共祖先
如果，判断是左右子树返回的是否是p,q那么，如果左右子树有一个子树出现了【最近公共祖先】
那这个结果会因为不是p,q而传递不上去。
反之，我们之和NULL做比较，只要不是NULL的都往上传，那无论在哪里找到了【最近公共祖先】
都会被递归返回上去。
*/
//得到了这个结点左右子树的值，就要判断这个结点是不是p,q的最近公共结点了
if (left != NULL && right != NULL) return root;//左右子树都不为空，说明左右子树返回的是p,q或者q,p具体顺序我们不关心
if (left != NULL && right == NULL) return left;//一个不为空，返回不为空的那个
else if (left == NULL && right != NULL) return right;//同理
else {
return NULL;//只剩下最后一种情况，左右两边都返回的是NULL
}
}