校招刷题群
高效刷题 迎战校招
校招精选试题
近年面笔经面经群内分享
Java刷题群 前端刷题群 产品运营群
首页 > 数据结构 > 二叉树遍历
题目

求二叉树两个结点的最低公共祖先节点,给出代码实现

解答

本道是大厂高频代码实现题,主要有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;
}


C 0条回复 评论

帖子还没人回复快来抢沙发