首页 > 数据结构 > 树形结构 > 寻找二叉树两个节点的最低公共祖先
2014
04-06

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

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

看下面的图就明白了:

 

lca

方法一

下面是一个简单的复杂度为 O(n) 的算法,解决LCA问题
1) 找到从根到n1的路径,并存储在一个向量或数组中。
2)找到从根到n2的路径,并存储在一个向量或数组中。
3) 遍历这两条路径,直到遇到一个不同的节点,则前面的那个即为最低公共祖先.

下面的C++的程序实现

// O(n) 解决 LCA
#include <iostream>
#include <vector>
using namespace std;

//二叉树节点
struct Node
{
    int key;
    struct Node *left, *right;
};
//公用函数,生成一个节点
Node * newNode(int k)
{
    Node *temp = new Node;
    temp->key = k;
    temp->left = temp->right = NULL;
    return temp;
}
//找到从root到 节点值为key的路径,存储在path中。没有的话返回-1
bool findpath(Node * root,vector<int> &path,int key){
	if(root == NULL) return false;
	path.push_back(root->key);
	if(root->key == key) return true;
	//左子树或右子树 是否找到,找到的话当前节点就在路径中了
	bool find =  ( findpath(root->left, path, key) || findpath(root->right,path ,key) );
	if(find) return true;
	//该节点下未找到就弹出
	path.pop_back();
	return false;
}

int findLCA(Node * root,int key1,int key2){
	vector<int> path1,path2;
	bool find1 = findpath(root, path1, key1);
	bool find2 = findpath(root, path2, key2);
	if(find1 && find2){
		int ans ;
		for(int i=0; i<path1.size(); i++){
			if(path1[i] != path2[i]){
				break;
			}else
				ans = path1[i];
		}
		return ans;
	}
	return -1;
}

// Driver program to test above functions
int main()
{
    // 按照上面的图来创创建树
    Node * root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
    cout << "LCA(4, 5) = " << findLCA(root, 4, 5);
    cout << "\nLCA(4, 6) = " << findLCA(root, 4, 6);
    cout << "\nLCA(3, 4) = " << findLCA(root, 3, 4);
    cout << "\nLCA(2, 4) = " << findLCA(root, 2, 4);
    return 0;
}

输出:

LCA(4, 5) = 2
LCA(4, 6) = 1
LCA(3, 4) = 1
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在左子树中,否则在右子树。

/* 只用一次遍历解决LCA */
#include <iostream>
using namespace std;
struct Node
{
    struct Node *left, *right;
    int key;
};
Node* newNode(int key)
{
    Node *temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return temp;
}

// 返回n1和n2的 LCA的指针
// 假设n1和n2都出现在树中
struct Node *findLCA(struct Node* root, int n1, int n2)
{
    if (root == NULL) return NULL;

    // 只要n1 或 n2 的任一个匹配即可
    //  (注意:如果 一个节点是另一个祖先,则返回的是祖先节点。因为递归是要返回到祖先的 )
    if (root->key == n1 || root->key == n2)
        return root;
    // 分别在左右子树查找
    Node *left_lca  = findLCA(root->left, n1, n2);
    Node *right_lca = findLCA(root->right, n1, n2);
    // 如果都返回非空指针 Non-NULL, 则说明两个节点分别出现了在两个子树中,则当前节点肯定为LCA
    if (left_lca && right_lca)  return root;
    // 如果一个为空,在说明LCA在另一个子树
    return (left_lca != NULL)? left_lca: right_lca;
}

//测试
int main()
{
    // 构造上面图中的树
    Node * root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
    cout << "LCA(4, 5) = " << findLCA(root, 4, 5)->key;
    cout << "\nLCA(4, 6) = " << findLCA(root, 4, 6)->key;
    cout << "\nLCA(3, 4) = " << findLCA(root, 3, 4)->key;
    cout << "\nLCA(2, 4) = " << findLCA(root, 2, 4)->key;
    return 0;
}

时间复杂度为O(n),但是上面的方法还是有所局限的,必须保证两个要查找的节点n1和n2都出现在树中。如果n1不在树中,则会返回n2为LCA,理想答案应该为NULL。要解决这个问题,可以先查找下 n1和n2是否出现在树中,然后加几个判断即可。

参考:http://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/


  1. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。

  2. 因为是要把从字符串s的start位到当前位在hash中重置,修改提交后能accept,但是不修改居然也能accept

  3. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮