游客 注册 | 登录
中文 | En

3651 - 树的路径

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB
给定一棵二叉树和两个不同的节点，求出他们到最近的公共祖先父节点的路径。已知该二叉树有n个节点，标号1..n。(n<100)

题目输入

输入：
第一行两个整数x，y，表示需要求的节点；
以下若干行，每行两个整数a和b，表示a的父节点是b。

题目输出

X到y的路径。

输入/输出样例

输入格式

9 7
2 1
3 2
4 2
5 3
8 5
9 5
6 4
7 4

输出格式

9 5 3 2 4 7

C语言解答

#include<stdio.h>

int pre[100];
int path1[100],path2[100];

int main(){
	int x,y,i,j,k;
	scanf("%d %d",&x,&y);
	int a,b;
	while(scanf("%d %d",&a,&b)==2){
		pre[a]=b;
	}
	i=j=0;
	path1[i]=x;
	path2[j]=y;
	while(pre[x]!=0){
		i++;
		path1[i]=pre[x];
		x=pre[x];
	}
	while(pre[y]!=0){
		j++;
		path2[j]=pre[y];
		y=pre[y];
	}
	while(path1[i]==path2[j]){
		i--;
		j--;
	}
	for(k=0;k<=i+1;k++){
		printf("%d ",path1[k]);
	}
	for(k=j;k>=0;k--){
		printf("%d ",path2[k]);
	}
}

C++解答

#include<cstdio>
#include<stack>
using namespace std;
const int N=100;
int x,y;
int f[N];
bool g[N];
stack<int>s;
int main()
{
	int a,b;
	scanf("%d%d",&x,&y);
	for(int i=1;i<N;i++)
		f[i]=i;
	while(scanf("%d%d",&a,&b)!=EOF&&a)
		f[a]=b;
	if(x==y)
		printf("%d",x);
	else
	{
		a=x,b=y;
		g[x]=true;
		while(x!=f[x])
			x=f[x],g[x]=true;
		while(g[y]!=true)
			y=f[y],s.push(y);
		g[y]=false;
		while(g[a]==true)
			printf("%d ",a),a=f[a];
		while(!s.empty())
			printf("%d ",s.top()),s.pop();
		printf("%d",b);
	}
	return 0;
}
请先登陆