剑指offer 86
详细解析:二叉树的最近公共祖先
题目:
给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 p和 q,请找到 p 和 q 的最近公共祖先节点。
自底向上搜索为后序遍历-------回溯算法思想
三种情况:
- 如果 p 和 q 都在以 root 为根的树中,函数返回的即使 p 和 q 的最近公共祖先节点。
- 那如果 p 和 q 都不在以 root 为根的树中 返回 null
- 很多人容易忽略的一个情况,就是节点本身p,它拥有一个子孙节点q
假设当找到一个节点是p(目标节点)的时候,直接返回当前目标节点,无需再继续递归子树,就算后序找到节点q(子孙节点),则p和q的公共节点还是p ! 所以无需再遍历!
如例中5是4的公共节点,遇到5直接返回5即可,无需再往下遍历到4,计算遍历到4,结果还是5。
本题递归有返回值,因为回溯的过程需要递归函数的返回值做判断
如果搜索整个树,则用变量left、right接住返回值,这个left、right后序还有逻辑处理的需要,也就是后序遍历中处理中间节点的逻辑(也是回溯)。
递归三部曲:
- 参数已给,返回值为root,这里用辅助函数
- 终止条件,root为 目标节点 p或者 q 或者null,直接返回root !
- 单层逻辑: 后序遍历,通过遍历的结果 left和right进行判断,
如果都不为null即root就是公共祖先(root左右各一个目标节点)!
如果都为null则为返回null ;
如果一方为null,另一方不为null,即不为null的是公共祖先
public class Solution {
public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
// 自底向上,后序遍历-----回溯
// 且用left和right记录递归的值
return check(root,o1,o2).val;
}
private TreeNode check(TreeNode root, int o1, int o2){
// 终止条件, 返回目标节点or null
if(root==null || root.val==o1 || root.val==o2){
return root;
}
TreeNode left=check(root.left,o1,o2);
TreeNode right=check(root.right,o1,o2);
// 利用left和right做判断
if(left!=null && right!=null){
return root; // 即root为公共祖先
}
if(left==null && right==null){
return null;
}
if(left==null){
return right;
}else{
return left;
} // 即不为null的是公共祖先
}
}



