`
gaotong1991
  • 浏览: 92825 次
  • 来自: 北京
社区版块
存档分类
最新评论

寻找二叉树两个节点的最低公共祖先

 
阅读更多

给定一棵树,同时给出树中的两个结点(n1和n2),求它们的最低公共祖先。也就是常见的LCA(Lowest Common Ancestor )问题。

看下面的图就明白了:

 

lca

方法一

下面是一个简单的复杂度为 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

2
1
分享到:
评论

相关推荐

    二叉树中最低公共祖先

    最低公共祖先问题是指给定两个节点,找到它们在二叉树中的最近公共祖先。这个公共祖先应当满足两个条件:一是它是两个给定节点的祖先,二是没有其他节点比它更接近这两个节点。这个问题在实际应用中很有价值,比如在...

    寻找二叉树两结点最近的祖先

    (1)拟定合适的二叉树的输入形式和构造算法; (2)能够以直观的形式观察所建立的二叉树的结构;

    二叉树最近最近公共祖先

    以下是一个简化的Java代码示例,演示了如何使用栈进行DFS来寻找二叉树中两个节点的最近公共祖先: ```java public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int val) { this.val ...

    二叉树中两结点最近的共同祖先算法

    对于每个节点,我们可以计算其祖先节点的集合,然后找到两个节点的最近公共祖先。 算法实现 我们使用Microsoft Visual C++ 6.0编译环境进行调试运行。首先,我们定义了一个二叉树的结构体,包括节点值、左孩子节点...

    LCA.tar.zip_二叉树的最近公共祖先问题

    要设计一个算法来找到二叉树中两个节点的最近公共祖先,我们可以考虑多种方法。这里我们将介绍两种常见的策略:深度优先搜索(DFS)和层次遍历(也称为广度优先搜索,BFS)。 1. **深度优先搜索(DFS)**: - 我们...

    使用C语言求二叉树结点的最低公共祖先的方法

    总结来说,求解二叉树节点的最低公共祖先,可以通过先求出两个节点到根节点的路径,然后找到路径上的最后一个相同节点;对于特殊的二叉排序树,可以利用其特性进行更高效的搜索。在ACM题目中,我们可以利用后序遍历...

    最低公共祖先算法实现

    最低公共祖先(Lowest Common Ancestor,简称LCA)算法是数据结构与算法中的一个重要概念,主要用于处理树形结构的问题,比如在二叉树、树状数组或图中找到两个节点的最近公共祖先。在本项目中,它通过C++语言实现,...

    编写算法在二叉排序树上找出任意两个不同节点的最近公共祖先.pdf

    具体来说,我们将从树的根节点开始,递归地遍历树,直到找到两个节点的最近公共祖先。 下面是算法的实现代码: ```c Bit *SearchBitree(Bit *T,int a,int b){ Bit *p,*q; p=q=T; while(p!=NULL){ if(a&lt;p-&gt;data&...

    二叉树的最近公共祖先II1

    二叉树的最近公共祖先定义如下:对于一棵有根树T中的两个节点p和q,最近公共祖先表示为一个节点x,这个节点x满足它是p和q的祖先,并且x的深度尽可能大(节点自身也可以是其自身的祖先)。 给定的代码实现了一个解决...

    编写算法在二叉排序树上找出任意两个不同节点的最近公共祖先.docx

    在主函数 `main` 中,首先调用 `SetBitree` 创建一个二叉排序树,然后提示用户输入两个节点数据,调用 `SearchBitree` 查找最近公共祖先,并打印结果。 总结起来,这个程序实现了在二叉排序树中查找两个节点最近...

    二叉树的最近公共祖先1

    给定一个二叉树和两个节点p和q,任务是找到这两个节点在树中的最近公共祖先。最近公共祖先(LCA)是指满足以下条件的节点x:x是p和q的祖先,并且x的深度尽可能大。如果节点x可以是它自己,那么它也可以是最近公共...

    数据结构求公共祖先

    此外,为了优化查询性能,可以采用预处理的方法,如LCA(Lowest Common Ancestor)数据结构,如Morris遍历或Tarjan's offline LCA算法,它们能在O(1)的时间复杂度内求解任意两个节点的最近公共祖先。 总结起来,求...

    python入门-leetcode面试题解之第236题二叉树的最近公共祖先.zip

    在二叉树中,最近公共祖先(LCA,Least Common Ancestor)是指两个节点在树中最高层次的共同父节点。此问题的解决方案通常需要遍历二叉树,可以采用深度优先搜索(DFS)或广度优先搜索(BFS)策略。 深度优先搜索是...

    common-father.rar_Father

    总之,寻找二叉树中两个节点的公共祖先是一个典型的计算机科学问题,通过深度优先搜索、广度优先搜索、哈希映射或自底向上的递归策略,我们可以高效地解决这个问题。理解这些方法不仅有助于解决实际问题,还能提高对...

    面试题68 – II. 二叉树的最近公共祖先

    百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)” 例如,给定如下二叉树: root = [3...

    二叉树交换左右子树 查询祖先结点

    二叉树是一种特殊的树结构,每个节点最多有两个子节点,分别称为左子节点和右子节点。在计算机科学中,二叉树常被用于数据存储、搜索、排序等多种任务,其性质和操作对于理解算法至关重要。 标题“二叉树交换左右...

    C++实现寻找最低公共父节点的方法

    在二叉树中,这个祖先节点必须同时是这两个节点的祖先,并且在路径从根节点到这两个节点的路径中,该节点距离根节点最近。 在上述C++实现中,作者提供了一种解决方案来寻找二叉树中的最低公共父节点。首先,他们...

    数据结构 求解公共祖先 C语言版

    标题中的“数据结构 求解公共祖先 C语言版”是指使用C语言实现一个数据结构相关的算法,目标是找出树中两个节点的最近公共祖先(Least Common Ancestor, LCA)。在计算机科学中,特别是在图论和数据结构领域,这个...

    二叉树是一种常见的数据结构,它由节点组成,每个节点最多有两个子节点,通常称为左子节点和右子节点 二叉树的创建和遍历是基础的计算

    它的基本概念基于节点的连接方式,每个节点最多包含两个子节点,一个被称为左子节点,另一个是右子节点。这种特殊的结构赋予了二叉树独特的性质和操作。 首先,我们来深入理解二叉树的构造。二叉树的构造通常分为两...

    题目整理(二叉树).pdf

    - 求两个节点的最低公共祖先节点。 - 求任意两节点的距离。 - 找出二叉树中某个节点的所有祖先节点。 4. 二叉树相关数据结构的定义: - 定义二叉树节点的结构体Node,以及二叉树的类型BiTree。 - 定义队列结构...

Global site tag (gtag.js) - Google Analytics