需求
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
示例 1:
输出:3
解释:节点 5
和节点 1
的最近公共祖先是节点 3 。
示例 2:
输出:5
解释:节点 5
和节点 4
的最近公共祖先是节点 5 。
因为根据定义最近公共祖先节点可以为节点本身。
示例 3:
输入:root = [1,2], p = 1, q = 2
输出:1
思路
遇到这个题目首先想的是要是能自底向上查找就好了,这样就可以找到公共祖先了。
那么二叉树如何可以自底向上查找呢?
回溯啊,二叉树回溯的过程就是从低到上。
后序遍历(左右中)就是天然的回溯过程,可以根据左右子树的返回值,来处理中节点的逻辑。
接下来就看如何判断一个节点是节点q和节点p的公共祖先呢。
首先最容易想到的一个情况:如果找到一个节点,发现左子树出现结点p,右子树出现节点q,或者 左子树出现结点q,右子树出现节点p,那么该节点就是节点p和q的最近公共祖先。 即情况一:
判断逻辑是 如果递归遍历遇到q,就将q返回,遇到p 就将p返回,那么如果 左右子树的返回值都不为空,说明此时的中节点,一定是q 和p 的最近祖先。
那么有录友可能疑惑,会不会左子树 遇到q 返回,右子树也遇到q返回,这样并没有找到 q 和p的最近祖先。
这么想的录友,要审题了,题目强调:二叉树节点数值是不重复的,而且一定存在 q 和 p。
但是很多人容易忽略一个情况,就是节点本身p(q),它拥有一个子孙节点q(p)。 情况二:
在递归函数有返回值的情况下:如果要搜索一条边,递归函数返回值不为空的时候,立刻返回,如果搜索整个树,直接用一个变量left、right接住返回值,这个left、right后序还有逻辑处理的需要,也就是后序遍历中处理中间节点的逻辑(也是回溯)。
那么为什么要遍历整棵树呢?直观上来看,找到最近公共祖先,直接一路返回就可以了。
就像图中一样直接返回7。
但事实上还要遍历根节点右子树(即使此时已经找到了目标节点了),也就是图中的节点4、15、20。
因为在如下代码的后序遍历中,如果想利用left和right做逻辑处理, 不能立刻返回,而是要等left与right逻辑处理完之后才能返回。
left = 递归函数(root->left); // 左
right = 递归函数(root->right); // 右
left与right的逻辑处理; // 中
所以此时大家要知道我们要遍历整棵树。知道这一点,对本题就有一定深度的理解了。
那么先用left和right接住左子树和右子树的返回值,代码如下:
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
如果left 和 right都不为空,说明此时root就是最近公共节点。这个比较好理解
如果left为空,right不为空,就返回right,说明目标节点是通过right返回的,反之依然。
这里有的同学就理解不了了,为什么left为空,right不为空,目标节点通过right返回呢?
如图:
图中节点10的左子树返回null,右子树返回目标值7,那么此时节点10的处理逻辑就是把右子树的返回值(最近公共祖先7)返回上去!
这里也很重要,可能刷过这道题目的同学,都不清楚结果究竟是如何从底层一层一层传到头结点的。
那么如果left和right都为空,则返回left或者right都是可以的,也就是返回空。
代码如下:
if (left == NULL && right != NULL) return right;
else if (left != NULL && right == NULL) return left;
else { // (left == NULL && right == NULL)
return NULL;
}
那么寻找最小公共祖先,完整流程图如下:
/**
* 236. 二叉树的最近公共祖先
* 公共祖先需要由下往上反值所以
* 使用后续遍历,左右中的方式将值返回到根节点得到结果
*/
public class LowestCommonAncestor236 {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 开始传入root 为null,或者遍历到叶子节点
if(root == null) return null;
// 叶子节点为P 或者 Q
if(root.val == p.val || root.val == q.val) return root;
// 左
TreeNode left = lowestCommonAncestor(root.left, p, q);
// 右
TreeNode right = lowestCommonAncestor(root.right, p , q);
// 中
// 代表找到了公共祖先向上反
if(left !=null && right!=null){ return root;
}
// 代表找到了P 或者Q
if(left ==null && right !=null){return right;
}else if(left !=null && right ==null){
//代表找打了P 或者Q
return left;
}else {
// 未找到P 或者 Q
return null;
}
}
}