已知中序后序遍历还原二叉树(uva 548) Apare_xzc

已知中序后序遍历还原二叉树

UVA 548 vjudge链接

2019/3/1 by xzc

为了给你们看一点儿干货，我写了一下午，有兴趣的看一看吧

^_^

节点为字母，还原二叉树代码演示

题意：
多组case,每组给出二叉树的中序遍历和后序遍历，还原这棵二叉树，并求出所有叶子节点中到根节点路径之和最小的叶子节点的值，若有多个这样的叶子节点，取其中值最小的
题面：

You are to determine the value of the leaf node in a given binary tree that is the terminal node of a
path of least value from the root of the binary tree to any leaf. The value of a path is the sum of values
of nodes along that path.
Input
The input file will contain a description of the binary tree given as the inorder and postorder traversal
sequences of that tree. Your program will read two line (until end of file) from the input file. The first
line will contain the sequence of values associated with an inorder traversal of the tree and the second
line will contain the sequence of values associated with a postorder traversal of the tree. All values
will be different, greater than zero and less than 10000. You may assume that no binary tree will have
more than 10000 nodes or less than 1 node.
Output
For each tree description you should output the value of the leaf node of a path of least value. In the
case of multiple paths of least value you should pick the one with the least value on the terminal node.

样例：

Sample Input
3 2 1 4 5 7 6
3 1 2 5 6 7 4
7 8 11 3 5 16 12 18
8 3 11 7 16 18 12 5
255
255
Sample Output
1
3
255

分析：
从最特殊的点开始入手，对于后序遍历序列，最后一个点即是根节点，我们可以在中序的序列中找到这一个点，并且这个根节点一定在中序序列中间某位置，其左右两边分别为左子树和右子树，我们查询出两个子树的大小，确定左右子树的范围后递归即可。

我的AC代码：(为了让你们看，用纯C语言写的 不知道你们会不会看)

/* 已知一棵二叉树的中序遍历和后序遍历，还原这棵二叉树 Author: xzc Username: XuZhichao Problem : UVA 548 Result : Accepted Time : 30ms Length : 2267 Submit Time: 2019-03-01 17:03:44 vj链接 : https://vjudge.net/problem/UVA-548 */
#include <stdio.h>
const int maxn = 100000+10; 
int POS[maxn]; //map<char,int> 字母在中序遍历中的位置 
struct Node{
	int val;
	int parents,Lchild,Rchild;//记录的是节点在node[]中的下标 
	bool isRchild; //它是否是其父节点的右子节点 
}node[maxn]; 
int InOrder[maxn];
int PostOrder[maxn];
int cnt,k;///cnt是新生成节点在node[]中的下标，K是后序遍历的下标 
int getTree(int fa,int isRchild);
void solve(int id,int sum);
int ans,leaves;
int main()
{
	//freopen("in1.txt","r",stdin);
	int n,x;
	char CH;
	while(scanf("%d",&x)!=EOF)
	{
		CH = getchar();
		InOrder[++n] = x;
		POS[x] = n;
		if(CH=='\n')
		{
			for(int i=1;i<=n;++i)
				scanf("%d",PostOrder+i);
			POS[0] = 0;
			InOrder[0] = 0;
			node[0].val = 0;
			k = n;
			cnt = 0;
			getTree(0,1);
			ans = 1e9;
			solve(1,0);	
			printf("%d\n",leaves);
			n = 0;	
		}
	}
	
	return 0;
}
//返回新节点在node中的下标 
int getTree(int fa,int isRchild) //该节点的父节点在node中的编号为fa 
{
	//printf("k = %d, getTree(%d,%c)\n",k,fa,isRchild?'R':'L');
	if(k<=0) return -1;
	int val1 = PostOrder[k];
	int pnow = POS[val1];
	int pfa  = POS[node[fa].val];
	if(isRchild) ///该节点被要求是fa节点的右子节点 
	{
		if(pnow<pfa) return -1; //在中序遍历中，它这个所谓的右子节点比所谓的父节点出现得还要靠前，矛盾
		--k; 
		int index = ++cnt;
		node[index].val = val1;
		node[index].parents = fa; 
		node[index].isRchild = true; 
		node[index].Rchild = getTree(index,1);
		node[index].Lchild = getTree(index,0);
		return index;//cnt是它自己所在节点的下标 
	}
	else ///该节点被要求是fa节点的左子节点 
	{
		int FirstRchild = fa;
		while(!node[FirstRchild].isRchild) 
		{
			FirstRchild = node[FirstRchild].parents;
		}
		FirstRchild = node[FirstRchild].parents; //它是向上回溯遇到的第一个右子节点的根节点 
		int POSOfGrandfa = POS[node[FirstRchild].val];
		if(pnow<POSOfGrandfa) return -1;
		--k;
		int index = ++cnt;
		node[index].val = val1;
		node[index].parents = fa;
		node[index].isRchild = false;
		node[index].Rchild = getTree(index,1);
		node[index].Lchild = getTree(index,0);
		return index;
	} 
	return -1;
} 
void solve(int id,int sum)
{
	if(id==-1) return;
	sum += node[id].val;
	if(node[id].Lchild==-1&&node[id].Rchild==-1)
	{
		if(ans>sum) ans = sum,leaves = node[id].val;
		if(ans==sum&&leaves>node[id].val) leaves = node[id].val; 
		return;
	}
	solve(node[id].Lchild,sum);
	solve(node[id].Rchild,sum);
}