二叉树的最近公共祖先()-其他

发表于： 3月 17, 2023 3月 17, 2023
分类：其他
标签：其他

二叉树的最近公共祖先()

一、简述

记录一下关于二叉树的最近公共祖先问题以及朴素算法。

二、二叉树的最近公共祖先

Daimayuan Online Judge.二叉树的最近公共祖先

题目描述

给你一棵 \(n\) 个节点的二叉树，节点的编号为 \(1\) 到 \(n\)，二叉树的根为 \(1\) 号节点。

读入 \(u,v\)，请求出 \(u\) 号节点和 \(v\) 号节点的最近公共祖先（\(Lowest\ Common\ Ancestor\)）。

如果 \(x\) 号节点既是 \(u\) 号节点的祖先也是 \(v\) 号节点的祖先，则称 \(x\) 号节点是 \(u\) 号节点和 \(v\) 号节点的公共祖先。

如果 \(x\) 号节点是 \(u\) 号节点和 \(v\) 号节点的所有公共祖先中深度最深的，则称 \(x\) 号节点是 \(u\) 号节点和 \(v\) 号节点的最近公共祖先。

输入格式

第一行一个整数 \(n\) 表示节点数。

接下来 \(n\) 行，每行两个整数，第一个整数表示 \(i\) 号节点的左儿子的编号，第二个整数表示 \(i\) 号节点的右儿子的编号，如果某个数字为 \(0\) 表示没有对应的子节点。

输入保证是一棵二叉树。

最后一行两个整数 \(u,v\) 表示要求最近公共祖先的两个节点的编号。

输出格式

输出一行一个整数，代表 \(u\) 号节点和 \(v\) 号节点的最近公共祖先。

数据范围

对于所有数据，保证 \(2≤n≤1000,1≤u,v≤n\)。

输入样例

输出样例

解题思路

简单的思路：从 \(u,v\) 往上逐渐到达根，分别存储二者追根路径上的点。然后同时从存储的最后的元素往前遍历，最后一个相同的元素就是二者最近公共祖先。
复杂的思路：将 \(u,v\) 先处理到同一层数，然后在同一层同时往上追根，第一个相同的元素就是最近公共祖先。笔者的代码实现的是这种思路。

以上两种做法仅限于数据范围较小的情况。后面的文章会介绍一下 \(Tarjan\) 算法。

C++代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
const int N = 5010;

int n;
int l[N], r[N], p[N], d[N], q[N];

int main()
{
	scanf("%d", &n);
	for(int  i = 1; i <= n; i ++)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		l[i] = x, r[i] = y;
		if(x)p[x] = i;
		if(y)p[y] = i;
	}
	int hh = 1, tt = 0;
	q[++ tt] = 1, d[1] = 1;
	while(hh <= tt)
	{
		int t = q[hh ++];
		if(l[t])
		{
			q[++ tt] = l[t];
			d[l[t]] = d[t] + 1;
		}
		if(r[t])
		{
			q[++ tt] = r[t];
			d[r[t]] = d[t] + 1;
		}
	}
	int u, v;
	scanf("%d%d", &u, &v);
	while(d[u] > d[v])
		u = p[u];
	while(d[v] > d[u])
		v = p[v];
	while(u != v)
		u = p[u], v = p[v];
	printf("%d", u);
	return 0;
}

————————