给定一棵树,同时给出树中的两个结点(n1和n2),求它们的最低公共祖先。也就是常见的LCA(Lowest Common Ancestor )问题。
看下面的图就明白了:
方法一
下面是一个简单的复杂度为 O(n) 的算法,解决LCA问题
1) 找到从根到n1的路径,并存储在一个向量或数组中。
2)找到从根到n2的路径,并存储在一个向量或数组中。
3) 遍历这两条路径,直到遇到一个不同的节点,则前面的那个即为最低公共祖先.
下面的C++的程序实现
01 |
// O(n) 解决 LCA |
02 |
#include <iostream> |
03 |
#include <vector> |
04 |
using namespace std;
|
05 |
06 |
//二叉树节点 |
07 |
struct Node
|
08 |
{ |
09 |
int key;
|
10 |
struct Node *left, *right;
|
11 |
}; |
12 |
//公用函数,生成一个节点 |
13 |
Node * newNode( int k)
|
14 |
{ |
15 |
Node *temp = new Node;
|
16 |
temp->key = k;
|
17 |
temp->left = temp->right = NULL;
|
18 |
return temp;
|
19 |
} |
20 |
//找到从root到 节点值为key的路径,存储在path中。没有的话返回-1 |
21 |
bool findpath(Node * root,vector< int > &path, int key){
|
22 |
if (root == NULL) return false ;
|
23 |
path.push_back(root->key);
|
24 |
if (root->key == key) return true ;
|
25 |
//左子树或右子树 是否找到,找到的话当前节点就在路径中了
|
26 |
bool find = ( findpath(root->left, path, key) || findpath(root->right,path ,key) );
|
27 |
if (find) return true ;
|
28 |
//该节点下未找到就弹出
|
29 |
path.pop_back();
|
30 |
return false ;
|
31 |
} |
32 |
33 |
int findLCA(Node * root, int key1, int key2){
|
34 |
vector< int > path1,path2;
|
35 |
bool find1 = findpath(root, path1, key1);
|
36 |
bool find2 = findpath(root, path2, key2);
|
37 |
if (find1 && find2){
|
38 |
int ans ;
|
39 |
for ( int i=0; i<path1.size(); i++){
|
40 |
if (path1[i] != path2[i]){
|
41 |
break ;
|
42 |
} else
|
43 |
ans = path1[i];
|
44 |
}
|
45 |
return ans;
|
46 |
}
|
47 |
return -1;
|
48 |
} |
49 |
50 |
// Driver program to test above functions |
51 |
int main()
|
52 |
{ |
53 |
// 按照上面的图来创创建树
|
54 |
Node * root = newNode(1);
|
55 |
root->left = newNode(2);
|
56 |
root->right = newNode(3);
|
57 |
root->left->left = newNode(4);
|
58 |
root->left->right = newNode(5);
|
59 |
root->right->left = newNode(6);
|
60 |
root->right->right = newNode(7);
|
61 |
cout << "LCA(4, 5) = " << findLCA(root, 4, 5);
|
62 |
cout << "\nLCA(4, 6) = " << findLCA(root, 4, 6);
|
63 |
cout << "\nLCA(3, 4) = " << findLCA(root, 3, 4);
|
64 |
cout << "\nLCA(2, 4) = " << findLCA(root, 2, 4);
|
65 |
return 0;
|
66 |
} |
输出:
1 |
LCA(4, 5) = 2 |
2 |
LCA(4, 6) = 1 |
3 |
LCA(3, 4) = 1 |
4 |
LCA(2, 4) = 2 |
时间复杂度: O(n), 树被遍历了两次,每次遍历复杂度不超过n,然后比较路径。
第二种方法(只遍历一次)
上面的方法虽然是O(n),但是操作依然繁琐了一点,并且需要额外的空间来存储路径。其实可以只遍历一次,利用递归的巧妙之处。学好二叉树,其实就是学好递归。
从root开始遍历,如果n1和n2中的任一个和root匹配,那么root就是LCA。 如果都不匹配,则分别递归左、右子树,如果有一个 key(n1或n2)出现在左子树,并且另一个key(n1或n2)出现在右子树,则root就是LCA. 如果两个key都出现在左子树,则说明LCA在左子树中,否则在右子树。
01 |
/* 只用一次遍历解决LCA */ |
02 |
#include <iostream> |
03 |
using namespace std;
|
04 |
struct Node
|
05 |
{ |
06 |
struct Node *left, *right;
|
07 |
int key;
|
08 |
}; |
09 |
Node* newNode( int key)
|
10 |
{ |
11 |
Node *temp = new Node;
|
12 |
temp->key = key;
|
13 |
temp->left = temp->right = NULL;
|
14 |
return temp;
|
15 |
} |
16 |
17 |
// 返回n1和n2的 LCA的指针 |
18 |
// 假设n1和n2都出现在树中 |
19 |
struct Node *findLCA( struct Node* root, int n1, int n2)
|
20 |
{ |
21 |
if (root == NULL) return NULL;
|
22 |
23 |
// 只要n1 或 n2 的任一个匹配即可
|
24 |
// (注意:如果 一个节点是另一个祖先,则返回的是祖先节点。因为递归是要返回到祖先的 )
|
25 |
if (root->key == n1 || root->key == n2)
|
26 |
return root;
|
27 |
// 分别在左右子树查找
|
28 |
Node *left_lca = findLCA(root->left, n1, n2);
|
29 |
Node *right_lca = findLCA(root->right, n1, n2);
|
30 |
// 如果都返回非空指针 Non-NULL, 则说明两个节点分别出现了在两个子树中,则当前节点肯定为LCA
|
31 |
if (left_lca && right_lca) return root;
|
32 |
// 如果一个为空,在说明LCA在另一个子树
|
33 |
return (left_lca != NULL)? left_lca: right_lca;
|
34 |
} |
35 |
36 |
//测试 |
37 |
int main()
|
38 |
{ |
39 |
// 构造上面图中的树
|
40 |
Node * root = newNode(1);
|
41 |
root->left = newNode(2);
|
42 |
root->right = newNode(3);
|
43 |
root->left->left = newNode(4);
|
44 |
root->left->right = newNode(5);
|
45 |
root->right->left = newNode(6);
|
46 |
root->right->right = newNode(7);
|
47 |
cout << "LCA(4, 5) = " << findLCA(root, 4, 5)->key;
|
48 |
cout << "\nLCA(4, 6) = " << findLCA(root, 4, 6)->key;
|
49 |
cout << "\nLCA(3, 4) = " << findLCA(root, 3, 4)->key;
|
50 |
cout << "\nLCA(2, 4) = " << findLCA(root, 2, 4)->key;
|
51 |
return 0;
|
52 |
} |
时间复杂度为O(n),但是上面的方法还是有所局限的,必须保证两个要查找的节点n1和n2都出现在树中。如果n1不在树中,则会返回n2为LCA,理想答案应该为NULL。要解决这个问题,可以先查找下 n1和n2是否出现在树中,然后加几个判断即可。
原文:http://www.acmerblog.com/lca-lowest-common-ancestor-5574.html
相关推荐
最低公共祖先问题是指给定两个节点,找到它们在二叉树中的最近公共祖先。这个公共祖先应当满足两个条件:一是它是两个给定节点的祖先,二是没有其他节点比它更接近这两个节点。这个问题在实际应用中很有价值,比如在...
(1)拟定合适的二叉树的输入形式和构造算法; (2)能够以直观的形式观察所建立的二叉树的结构;
以下是一个简化的Java代码示例,演示了如何使用栈进行DFS来寻找二叉树中两个节点的最近公共祖先: ```java public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int val) { this.val ...
对于每个节点,我们可以计算其祖先节点的集合,然后找到两个节点的最近公共祖先。 算法实现 我们使用Microsoft Visual C++ 6.0编译环境进行调试运行。首先,我们定义了一个二叉树的结构体,包括节点值、左孩子节点...
要设计一个算法来找到二叉树中两个节点的最近公共祖先,我们可以考虑多种方法。这里我们将介绍两种常见的策略:深度优先搜索(DFS)和层次遍历(也称为广度优先搜索,BFS)。 1. **深度优先搜索(DFS)**: - 我们...
总结来说,求解二叉树节点的最低公共祖先,可以通过先求出两个节点到根节点的路径,然后找到路径上的最后一个相同节点;对于特殊的二叉排序树,可以利用其特性进行更高效的搜索。在ACM题目中,我们可以利用后序遍历...
最低公共祖先(Lowest Common Ancestor,简称LCA)算法是数据结构与算法中的一个重要概念,主要用于处理树形结构的问题,比如在二叉树、树状数组或图中找到两个节点的最近公共祖先。在本项目中,它通过C++语言实现,...
具体来说,我们将从树的根节点开始,递归地遍历树,直到找到两个节点的最近公共祖先。 下面是算法的实现代码: ```c Bit *SearchBitree(Bit *T,int a,int b){ Bit *p,*q; p=q=T; while(p!=NULL){ if(a<p->data&...
二叉树的最近公共祖先定义如下:对于一棵有根树T中的两个节点p和q,最近公共祖先表示为一个节点x,这个节点x满足它是p和q的祖先,并且x的深度尽可能大(节点自身也可以是其自身的祖先)。 给定的代码实现了一个解决...
在主函数 `main` 中,首先调用 `SetBitree` 创建一个二叉排序树,然后提示用户输入两个节点数据,调用 `SearchBitree` 查找最近公共祖先,并打印结果。 总结起来,这个程序实现了在二叉排序树中查找两个节点最近...
给定一个二叉树和两个节点p和q,任务是找到这两个节点在树中的最近公共祖先。最近公共祖先(LCA)是指满足以下条件的节点x:x是p和q的祖先,并且x的深度尽可能大。如果节点x可以是它自己,那么它也可以是最近公共...
此外,为了优化查询性能,可以采用预处理的方法,如LCA(Lowest Common Ancestor)数据结构,如Morris遍历或Tarjan's offline LCA算法,它们能在O(1)的时间复杂度内求解任意两个节点的最近公共祖先。 总结起来,求...
在二叉树中,最近公共祖先(LCA,Least Common Ancestor)是指两个节点在树中最高层次的共同父节点。此问题的解决方案通常需要遍历二叉树,可以采用深度优先搜索(DFS)或广度优先搜索(BFS)策略。 深度优先搜索是...
总之,寻找二叉树中两个节点的公共祖先是一个典型的计算机科学问题,通过深度优先搜索、广度优先搜索、哈希映射或自底向上的递归策略,我们可以高效地解决这个问题。理解这些方法不仅有助于解决实际问题,还能提高对...
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)” 例如,给定如下二叉树: root = [3...
二叉树是一种特殊的树结构,每个节点最多有两个子节点,分别称为左子节点和右子节点。在计算机科学中,二叉树常被用于数据存储、搜索、排序等多种任务,其性质和操作对于理解算法至关重要。 标题“二叉树交换左右...
在二叉树中,这个祖先节点必须同时是这两个节点的祖先,并且在路径从根节点到这两个节点的路径中,该节点距离根节点最近。 在上述C++实现中,作者提供了一种解决方案来寻找二叉树中的最低公共父节点。首先,他们...
标题中的“数据结构 求解公共祖先 C语言版”是指使用C语言实现一个数据结构相关的算法,目标是找出树中两个节点的最近公共祖先(Least Common Ancestor, LCA)。在计算机科学中,特别是在图论和数据结构领域,这个...
它的基本概念基于节点的连接方式,每个节点最多包含两个子节点,一个被称为左子节点,另一个是右子节点。这种特殊的结构赋予了二叉树独特的性质和操作。 首先,我们来深入理解二叉树的构造。二叉树的构造通常分为两...
- 求两个节点的最低公共祖先节点。 - 求任意两节点的距离。 - 找出二叉树中某个节点的所有祖先节点。 4. 二叉树相关数据结构的定义: - 定义二叉树节点的结构体Node,以及二叉树的类型BiTree。 - 定义队列结构...