求二叉树两节点的LCA(最近公共祖先)(必须要会+常考)+求叶子节点到LCA的距离+求两个叶子节点之间的距离
程序员文章站
2024-03-15 11:09:49
...
- 两个节点分别在最近公共祖先的左子树上
- 两个节点分别在最近公共祖先的右子树上
- 其中一个节点同时在最近公共祖先的左子树或者有子树上(当从根节点开始遍历到一个节点A等于这两个节点中的其中一个节点,A即为最近祖先节点)
二叉树中任意两个节点的最近祖先节点(LCA):
最近祖先节点就是从根节点遍历到给定节点时的最后一个相同节点。
如上图,H和J的最低祖先节点是A。
因为从根节点Root到H的链路为: Root A C H
从根节点Root到J的链路为: Root A D J
查看链路节点可知,A是最后一个相同节点,也就是最近公共父节点或者说最低祖先节点是A。
实现LCA有两种方式,递归和非递归,此处仅介绍递归方式。
LCA思路:
-
如果给定pRoot是NULL,即空树,则返回的公共节点自然就是NULL;
-
如果给定pRoot与两个节点中任何一个相同,说明,pRoot在就是所要找的两个节点之一,则直接返回pRoot,表明在当前链路中找到至少一个节点;
-
如果给定pRoot不是两个节点中任何一个,则说明,需要在pRoot的左、右子树中重新查找,此时有三种情况:两个节点都在左子树上;两个节点都在右子树上;一个在左子树,一个在右子树上;具体来说,就是:
-
情况一:如果左子树查找出的公共节点是NULL,则表明从左子树根节点开始到左子树的所有叶子节点等所有节点中,没有找到两个节点中的任何一个,这就说明,这两个节点不在左子树上,不在左子树,则必定在右子树上;
-
情况二:如果右子树查找的公共节点是NULL,说明在右子树中无法找到任何一个节点,则两个节点必定在左子树上;
-
情况三: 如果左右子树查找的公共节点都不是NULL,说明左右子树中各包含一个节点,则当前节点pRoot就是最近公共节点,返回就可以了。
注意: 三种情况是互斥的, 只能是其中之一。
-
public TreeNode GetLastCommonParent( TreeNode pRoot, TreeNode pNode1, TreeNode pNode2){
if( pRoot == null ) //说明是空树,不用查找了,也就找不到对应节点,则返回NULL
return null;
if( pRoot == pNode1 || pRoot == pNode2 )//说明在当前子树的根节点上找到两个节点之一
return pRoot;
TreeNode pLeft = GetLastCommonParent( pRoot.left, pNode1, pNode2); //左子树中的查找两个节点并返回查找结果
TreeNode pRight = GetLastCommonParent( pRoot.right, pNode1, pNode2);//右子树中查找两个节点并返回查找结果
if( pLeft == null )//如果在左子树中没有找到,则断定两个节点都在右子树中,可以返回右子树中查询结果;否则,需要结合左右子树查询结果共同断定
return pRight;
if ( pRight == null )//如果在右子树中没有找到,则断定两个节点都在左子树中,可以返回左子树中查询结果;否则,需要结合左右子树查询结果共同断定
return pLeft;
return pRoot;//如果在左右子树中都找两个节点之一,则pRoot就是最近公共祖先节点,返回即可。
}
求节点值最大、最小的叶子节点之间的距离
扩展:求任意两个叶子节点到LCA的距离(使用以下方法,传入不同的参数)
import java.util.*;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}*/
public class Tree {
private TreeNode maxNode = new TreeNode(Integer.MIN_VALUE);
private TreeNode minNode = new TreeNode(Integer.MAX_VALUE);
public int getDis(TreeNode root) {
// write code here
getMaxMin(root);//找到最大最小叶子节点
TreeNode lcaNode = getLCA(root);//找LCA
int a = getNodeDis(lcaNode, maxNode);//最大值叶子节点到LCA的距离;
int b = getNodeDis(lcaNode, minNode);//最小值叶子节点到LCA的距离;
return a+b;
}
// 先找到最大最小叶子节点
public void getMaxMin(TreeNode root) {
if (root == null) {
return;
}
if (root.left == null && root.right == null) {
if (root.val > maxNode.val) {
maxNode = root;
} else if (root.val < minNode.val) {
minNode = root;
}
}
getMaxMin(root.left);
getMaxMin(root.right);
}
// LCA最近公共祖先
public TreeNode getLCA(TreeNode root) {
if (root == null) {// 说明是空树
return null;
}
if (root.val == maxNode.val || root.val == minNode.val) {// 在当前树的根节点上找到两个节点之一
return root;
}
TreeNode leftNode = getLCA(root.left);// 左子树中的查找两个节点并返回查找结果
TreeNode rightNode = getLCA(root.right);// 右子树中查找两个节点并返回查找结果
if (leftNode == null) {// 左子树中没找到,则一定在右子树上
return rightNode;
} else if (rightNode == null) {// 右子树没找到一定在左子树上
return leftNode;
} else {// 左右子树均找到一个节点,则根节点为最近公共祖先
return root;
}
}
//获取叶子节点到LCA距离
public int getNodeDis(TreeNode lcaNode, TreeNode node){
if(lcaNode==null){
return -1;
}
if(lcaNode.val==node.val){
return 0;
}
//三种情况:两个均在左子树;两个均在右子树;一左一右,所以不能用if-elseif结构
int distance = getNodeDis(lcaNode.left, node);//左子树未找到两个节点之一
if(distance==-1){
distance = getNodeDis(lcaNode.right, node);
}
if(distance!=-1){
return distance+1;
}
return -1;
}
上一篇: 微信小程序父组件获取子组件的点击事件——子组件给父组件传值
下一篇: Servlet下页面跳转方式