解答
本道是大厂高频代码实现题,主要有3个核心点
1.对每个结点的孩子进行递归遍历,如果左孩子里一个需求结果都没有,就不是祖先节点
2.如果两个结点都在一侧出来,也不是最低祖先结点。
3.最低孩子结点只可能是一左一右,而且具体镜像性,就是可以结点1在左,也可能结点2在左,不要忘记加一个else
TreeNode getLastCommonParent(TreeNode root,TreeNode t1,TreeNode t2){
if(findNode(root.left,t1)){
if(findNode(root.right,t2)){
return root;
}else{
return getLastCommonParent(root.left,t1,t2);
}
}else{
if(findNode(root.left,t2)){
return root;
}else{
return getLastCommonParent(root.right,t1,t2)
}
}
}
// 查找节点node是否在当前 二叉树中
boolean findNode(TreeNode root,TreeNode node){
if(root == null || node == null){
return false;
}
if(root == node){
return true;
}
boolean found = findNode(root.left,node);
if(!found){
found = findNode(root.right,node);
}
return found;
}
帖子还没人回复快来抢沙发