`
eriol
  • 浏览: 407281 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

二叉树中两个节点的最近公共祖先

LCA 
阅读更多

求二叉树中任意两个节点的最近公共祖先也称为LCA问题(Lowest Common Ancestor)。

 

 

二叉查找树

 

如果该二叉树是二叉查找树,那么求解LCA十分简单。

基本思想为:从树根开始,该节点的值为t,如果t大于t1和t2,说明t1和t2都位于t的左侧,所以它们的共同祖先必定在t的左子树中,从t.left开始搜索;如果t小于t1和t2,说明t1和t2都位于t的右侧,那么从t.right开始搜索;如果t1<t< t2,说明t1和t2位于t的两侧,那么该节点t为公共祖先。

如果t1是t2的祖先,那么应该返回t1的父节点;同理,如果t2是t1的祖先,应该返回t2的父节点。

 

public int query(Node t1, Node t2, Node t) {
	int left = t1.value;
	int right = t2.value;
	Node parent = null;
		
	if (left > right) {
		int temp = left;
		left = right;
		right = temp;
	}
		
	while (true) {
		if (t.value < left) {
			parent = t;
			t = t.right;
		} else if (t.value > right) {
			parent = t;
			t = t.left;
		} else if (t.value == left || t.value == right) {
			return parent.value;
		} else {
			return t.value;
		}
	}
}

 

    其中,parent用于处理t1是t2的祖先(或t2是t1的祖先)的情况。

 

 

一般的二叉树

 

如果二叉树不是二叉查找树该怎么办呢?

 

 

1. 离线算法(Tarjan)

利用并查集优越的时空复杂度,可以实现O(n+q)的算法,q是查询次数。

Tarjan算法基于深度优先搜索。对于新搜索到的一个结点u,先创建由u构成的集合,再对u的每颗子树进行搜索,每搜索完一棵子树,这时候子树中所有的结点的最近公共祖先就是u了。

 

void LCA(int parent)       //从根节点开始
{
	p[parent] = parent;
	ancestor[findSet(parent)] = parent;
	for(int i = index[parent]; i != -1; i = e[i].next)
	{
		LCA(e[i].to);
		Union(parent,e[i].to);
		ancestor[findSet(parent)] = parent;
	}
	vis[parent] = true;
	if(parent == a && vis[b])	//要先将所有查询记录下来,这里只有一个查询:a与b的LCA
		printf("%d\n",ancestor[findSet(b)]);
	else if(parent == b && vis[a])
		printf("%d\n",ancestor[findSet(a)]);
}

 

 

2. 在线算法(RMQ)

一个O(nlog2n)的预处理,O(1)的查询。

以下面一棵树为例:

           (1)
         /     \
       (2)     (7)
      /   \       \
    (3)  (4)     (8)
          /   \
         (5)  (6)

step1:


    按深度遍历树,记录访问顺序和相应的深度(2*n-1),及每个节点第一次出现的位置。


    结点的访问顺序为:1 2 3 2 4 5 4 6 4 2 1 7 8 7
    相应的深度为:    0 1 2 1 2 3 2 3 2 1 0 1 2 1 0
    结点1-8第一次出现的次序为:1 2 3 5 6 8 12 13

step2:

    查询3和6的公共祖先,考虑3和6第一次出现的位置为3和8,即寻找序列2 1 2 3 2 3中的最小值,最小值为1,对应的点位2,则3与6的最近公共祖先为2。

step3:

    则对于给出的任意两个结点,找出它们第一次出现的位置i,j(i<j),在深度序列中查询最小值的下标k,depth[k]即为所求。显然,查询多次深度序列中的最小值的下标,自然而然就想到了RMQ。

 

public class LCA {
	
	private final int MAX = 10;
	private int[] dfs = new int[2*MAX];
	private int[] depth = new int[2*MAX];
	private int[][] f;
	private int[] call = new int[MAX];
	private int len = 0;
	
	public void track(Node t, int d) {
		if (t == null)
			return;
		dfs[len] = t.value;
		depth[len] = d;
		call[t.value-1] = len;
		len++;
		
		track2(t.left, d+1);
		if (t.left != null) {
			dfs[len] = t.value;
			depth[len] = d;
			len++;
		}
		
		track2(t.right, d+1);
		if (t.right != null) {
			dfs[len] = t.value;
			depth[len] = d;
			len++;
		}
	}
	
	public void rmq() {
		int count = 1;
		while ((1 << count) <= len)
			count++;
		f = new int[len][count];
		count--;
		
		for (int i = 0; i < len; i++) {
			f[i][0] = i;
		}
		
		for (int j = 1; (1 << j) <= len; j++) {
			for (int i = 0; i+(1<<j)-1 < len; i++) {
				f[i][j] = depth[f[i][j-1]] < depth[f[i+(1<<j-1)][j-1]] ? 
						f[i][j-1] : f[i+(1<<j-1)][j-1];
			}
		}
	}
	
	public int query(Node t1, Node t2) {
		int start = call[t1.value-1];
		int end = call[t2.value-1];
		
		if(start > end) {
			int temp = start;
			start = end;
			end = temp;
		}
		
		int count = 1;
		while ((1 << count) <= end - start + 1) 
			count++;
		count--;
		int result = depth[f[start][count]] < depth[f[end-(1<<count)+1][count]] ?
				f[start][count] : f[end-(1<<count)+1][count];
		
		if (dfs[result] == t1.value || dfs[result] == t2.value) {
			int temp = depth[result];
			while (depth[result] >= temp)
				result--;
		}
		return dfs[result];	
	}
	
	public static void main(String[] args) {
		Node n3 = new Node(3);
		Node n5 = new Node(5);
		Node n6 = new Node(6);
		Node n4 = new Node(4, n5, n6);
		Node n2 = new Node(2, n3, n4);
		Node n8 = new Node(8);
		Node n7 = new Node(7, null, n8);
		Node n1 = new Node(1, n2, n7);
		
		LCA l = new LCA();
		l.track(n1, 0);
		l.rmq();

		System.out.println(l.query(n5, n4));	
	}
}

class Node {
	int value;
	Node left;
	Node right;
	
	public Node(int value, Node left, Node right) {
		this.value = value;
		this.left = left;
		this.right = right;
	}
	
	public Node(int value) {
		this.value = value;
		this.left = null;
		this.right = null;
	}
}

 

 

3. 后序遍历

 

基本思想:如果这两个节点不在一条线上(即这两个节点不存在一个节点是另一个节点的祖先的情况),则它们必定分别在所求节点A的左子树和右子树上,后序遍历到第一个满足这个条件的节点就是所要求的节点A。否则,当这两个节点在一条线上,所求节点A则是这两个节点中深度最低的节点的父节点。

 

bool lca(Node *root, int va, int vb, Node *&result, Node* parent)
{
    // left/right 左/右子树是否含有要判断的两节点之一 
    bool left = false, right = false;
    if (!result && root->left) left = lca(root->left,va,vb,result,root);
    if (!result && root->right) right = lca(root->right,va,vb,result,root);

    // mid 当前节点是否是要判断的两节点之一 
    bool mid = false;
    if (root->data == va || root->data == vb) mid=true;
    if (!result && int(left + right + mid) == 2) {
        if (mid) result = parent;
        else result = root;
    }
    return left | mid | right ;
}

Node *query(Node *root,int va, int vb)
{
    if (root == NULL) return NULL;
    Node *result = NULL;
    lca(root, va, vb,result, NULL);
    return result;
}
 

 

分享到:
评论

相关推荐

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

    在遍历过程中,我们记录每个节点的祖先节点,并计算两个节点的最近公共祖先。 算法优化 为了提高算法的效率,我们可以对算法进行优化。例如,我们可以使用哈希表来存储每个节点的祖先节点,以便快速查找两个节点的...

    二叉树最近最近公共祖先

    在二叉树中,最近公共祖先(最近共同祖先,LCA,Lowest Common Ancestor)是指两个节点在树中的最近的共同父节点。在某些应用场景,如文件系统或社交网络中,找到最近公共祖先具有重要意义。 针对给定的"二叉树最近...

    二叉树中最低公共祖先

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

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

    最近公共祖先指的是在一棵树中,两个节点的共同祖先中离叶子节点最远的一个。解决这个问题在实际应用中有着广泛的应用,比如在文件系统中查找共同父目录,或者在社交网络中寻找共同好友等。 要设计一个算法来找到...

    二叉树的最近公共祖先II1

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

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

    在本算法中,我们将使用递归方法来查找两个节点的最近公共祖先。具体来说,我们将从树的根节点开始,递归地遍历树,直到找到两个节点的最近公共祖先。 下面是算法的实现代码: ```c Bit *SearchBitree(Bit *T,int a...

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

    总结起来,这个程序实现了在二叉排序树中查找两个节点最近公共祖先的功能。通过理解二叉排序树的性质和递归插入方法,我们可以有效地在树中定位和操作节点。在实际应用中,这种查找最近公共祖先的问题在数据结构和...

    二叉树的最近公共祖先1

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

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

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

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

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

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

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

    数据结构求公共祖先

    然后,当我们找到给定的两个节点时,可以通过比较它们在路径数组中的位置来确定最近的公共祖先。 以下是C语言实现的基本步骤: 1. 初始化一个空栈,用于存储DFS过程中的节点。 2. 从根节点开始进行深度优先搜索,...

    common-father.rar_Father

    在二叉树中,公共祖先是指在树中存在至少两个节点,它们都位于这个祖先节点的下方。这个问题通常在需要找出两个节点最近的共同祖先时出现,比如在文件系统中查找两个文件夹的最近共同父文件夹,或者在社交网络中查找...

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

    在ACM题目中,给定一颗树的先序遍历序列和两个节点值,我们需要找出这两个节点的最低公共祖先。这个问题可以通过后序遍历的思想解决,利用栈来保存路径,然后找到两个路径的第一个公共节点。这里给出一个基于后序...

    【POJ1330】最近公共祖先(LCA):并查集+深搜 - cxllyg的专栏 - 博客频道 - CSDN.NET1

    最近公共祖先(Lowest Common Ancestor,简称LCA)是指在一颗树中,两个指定节点的最近的共同祖先。这个问题在计算机科学,尤其是数据结构和算法领域中非常常见,特别是在处理二叉树时。本文将详细探讨三种不同情况...

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

    第235题的题目大致是这样的:给定一个BST的根节点和两个不同的节点值,目标是找到这两个节点在树中的最近公共祖先。公共祖先是指一个节点,使得所有路径到这两个给定节点都必须经过这个节点。如果一个节点同时是两个...

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

    最近公共祖先是指在树形结构中,两个节点的共同祖先中离叶子节点最近的一个。 在这个C语言程序中,我们可以看到一个简单的实现。首先,程序包含了两个头文件`stdio.h`和`conio.h`,前者用于标准输入输出,后者包含...

    Easay#JavascriptCoding#剑指68-2.二叉树的最近公共祖先1

    百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节

    Cygra#Leet-Code-Solus#0236. 二叉树的最近公共祖先1

    百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节

    floatLig#JavaLearning#236.二叉树的最近公共祖先1

    中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以

Global site tag (gtag.js) - Google Analytics