推断二叉树（进阶）

szz123 / 2024-10-23 / 原文

Description

给出一棵二叉树的中序遍历和每个节点的父节点，求这棵二叉树的先序和后序遍历。

Input

输入第一行为一个正整数 n 表示二叉树的节点数目，节点编号从 1 到 n，其中 1 为根节点。
第 2 行有 n 个数字，第 i 个数字表示 i 的父亲节点。（ 1 的父亲节点为 0，表示无）
第 3 行为中序遍历。
30%的数据： n<=20；
60%的数据： n<=1000；
100%的数据： n<=10000；

Output

输出 2 行，第一行为先序遍历，第二行为后序遍历。

Sample Input

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

Sample Output

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

思路

存下每个节点的左右儿子，然后根据中序遍历判断谁是左儿子，谁是右儿子，建完树，跑一下先序遍历和后序遍历

#include<iostream>
using namespace std;
const int N = 10010;
int lson[N], rson[N];//存结点x的左右儿子
int last[N];

void PreOrder(int x)
{
	//题目给定1为根
	if (x != 1) cout << " ";
	cout << x;
	if (lson[x]) PreOrder(lson[x]);
	if (rson[x])PreOrder(rson[x]);
}

bool flag = true;
void PostOrder(int x)
{
	if (lson[x]) PostOrder(lson[x]);
	if (rson[x])PostOrder(rson[x]);
	if (flag) cout << x;
	else cout<<" " << x;

	flag = false;
}


int main() {
	int n;
	cin >> n;
	int tmp;
	//先默认存左，左存了就存右
	for (int i = 1; i <= n; i++)
	{	
		cin >> tmp;
		if (!tmp)continue;
		if (!lson[tmp]) lson[tmp] = i;
		else rson[tmp] = i;
	}

	//last存tmp出现的先后,i表示先后
	for (int i = 1; i <= n; i++)
	{
		cin >> tmp;
		last[tmp] = i;
	}

	for (int i = 1; i <= n; i++)
	{
		if (lson[i] && rson[i])
		{
			//左根右
			if (last[rson[i]] < last[lson[i]])
			{
				swap(lson[i], rson[i]);
			}
		}
		//左根右 如果rson[i](只是个值)在根前， 那就是右儿子
		else if (!lson[i] && rson[i])
		{
			if (last[rson[i]] < last[i])
			{
				lson[i] = rson[i];
				rson[i] = 0;
			}
		}
		else if (lson[i] && !rson[i])
		{
			if (last[lson[i]] > last[i])
			{
				rson[i] = lson[i];
				lson[i] = 0;
			}
		}
	}

	PreOrder(1); cout << endl;
	PostOrder(1); cout << endl;

}