问题:
给定一个二叉树,找到两个节点NA, NB的最近公共祖先(LCA)。
比如对于下图,4 和 7 的 LCA 是6, 1和13的LCA 是 8。
我们这里先考虑一般的二叉树(BT),然后再考虑这个二叉树是二叉搜索树(BST)的情况。
查找两个node的最早的公共祖先,分三种情况:
1. 如果两个node在root的两边,那么最早的公共祖先就是root。
2. 如果两个node在root的左边,那么把root.leftChild作为root,再递归。
3.如果两个node在root的右边,那么把root.rightChild作为root,再递归。
那么我们如何知道能否通过原始节点到达某一个节点呢?这里我们需要定义一个递归函数covers (Node root, Node node),让root的左右子节点不断的调用这个函数,如果某一个子节点就是要找到的节点,那么返回true,否则返回false. 具体代码如下:
/*
* check whether the node n is in the tree
*/
private static boolean covers(Node rootNode, Node n) {
if(rootNode == null) return false;
if(rootNode == n) return true;
return covers(rootNode.leftChild, n) || covers(rootNode.rightChild, n);
}
有个covers这个函数,我们要实现前面三种不同的情况,那就简单了。代码如下:
/*
* get the first common ancestor of node p and node q
*/
public static Node commonAncestor(Node rootNode, Node p, Node q) {
// case 2
if (covers(rootNode.leftChild, p) && covers(rootNode.leftChild, q))
return commonAncestor(rootNode.leftChild, p, q);
//case 3
if (covers(rootNode.rightChild, p) && covers(rootNode.rightChild, q))
return commonAncestor(rootNode.rightChild, p, q);
//case 1
return rootNode;
}
如果这个二叉树是BST,那么我们可以利用BST的特点,把根节点的值与两个节点的值进行比较,如果两个节点的值都比根节点的值小,那么一定在根节点的左边,所以我们把根节点的左子节点作为起始点,然后递归。如果两个节点的值都比祖先节点的值大,那么一定在根节点的右边,所以我们把根节点的右子节点作为起始点,然后递归,如果上面两张情况都不是,那么很明显,这个根节点就是LCA.
代码如下:
public Node LCA(Node root, Node p, Node q) {
if (root == null || p == null || q == null ) return NULL;
if (max(p.data, q.data) < root.data)
return LCA(root.left, p, q);
else if (min(p.data, q.data) > root.data)
return LCA(root.right, p, q);
else
return root;
}
备注:这里并没有考虑 p 和 q 不在 BST里的情况。
分享到:
相关推荐
设计一个算法,对于给定的树中2 结点返回它们的最近公共祖先。 对于给定的树,和树中结点对,编程计算结点对的最近公共祖先。
LCA Tarjan: 实现原理 理解:离线算法,建好树后再查询,一次DFS 吧所有查询解决完。 时间复杂度:O(n+q); n个点 q次询问 补一下:链式向前星,并查集 ,Tarjan 代码 #include #include #include #include #...
lca用来求最近公共祖先,主要运用的是并查集的思想
RMQ以及LCA:最近公共祖先 解析及P解法 (ZFrom Internet)
。。。
最近公共祖先(LCA)板子代码
最近公共祖先LCA(链剖) 给定一棵 以 sss 为根节点,共有 nnn 个点的树。 有 mmm 次查询 每次查询 u,vu ,vu,v 的最近公共祖先。 算法流程 111.根据连边的信息建图(邻接表)。代码就不贴了,注意建立双向边。 222....
2. bool nodePath (bstNode* pRoot, int value, std::vector*>& path) 3. { 6
用St表实现对最近公共祖先LCA的运算与查询
最近公共祖先(LCA),转化为 RMQ 用线段树解决
数据泄密(泄露)防护(Data leakage prevention, DLP),又称为“数据丢失防护”(Data Loss prevention, DLP),有时也称为“信息泄漏防护”(Information leakage prevention, ILP)。数据泄密防护(DLP)是通过一定的...
设计一个算法,对于给定的树中2 结点返回它们的最近公共祖先。
LCA生命周期评价,LCA生命周期评价课件,LCA生命周期评价PPT
基于分治思想,利用并查集实现LCA(最近公共祖先)算法
Tarjan算法求最近公共祖先,输入树和询问,按询问顺序回答
原文来自于http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor。 翻译成中文。 LCA RMQ
lca_com.huawei.health.2305261058.apk-1-1686474870171.apk
lca_com.lenovo.leos.appstore.pad-120430-1705035641297.apk
lca_com.lenovo.leos.appstore.pad-120420-1703291160942.apk
tarjan离线算法求最近公共祖先。对于有根树T的两个结点u、v,最近公共祖先LCA(T