UVa 548 - Tree

紫书例题

题意：给一棵点带权（权各不相同，都是正整数）二叉树的中序和后序遍历，找一个叶子使得它到根的路径上的权和最小。如果有多解，该叶子本身的权应尽量小

算法：递归建树，然后DFS。注意，直接递归求结果也可以，但是先建树的方法不仅直观，而且更好调试

思路

重点:后序遍历的最后一个结点就是根节点
接下来，在中序遍历的序列中找到根节点，根节点前面的就是左子树，后面则是右子树
用同样的思路递归建二叉树

解题情况

因为各个结点的权值各不相同且都是正整数，直接用权值作为结点编号
用中序遍历和后序遍历的结点建树，返回树根root
dfs查找，在遇到叶子(没有左子树和右子树的结点)时停下，更新当前最小权值和与叶子最小权
因为要取最小值，初始化best_sum时，要赋值够大

读入小技巧：先getline(),再用string stream把line中的每一个数字压入数组

源码

// UVa 548 - Tree
// Written on 2021.1.27
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
using namespace std;

// 因为各个结点的权值各不相同且都是正整数，直接用权值作为结点编号
const int maxv=10000+10;
int in_order[maxv],post_order[maxv],lch[maxv],rch[maxv];
int n;

bool read_list(int* a){
	string line;
	if(!getline(cin,line)) return false;
	stringstream ss(line);
	n=0;
	int x;
	while(ss>>x) a[n++]=x;
	return n>0;
}

// 把in_order[L1..R1]和post_order[L2..R2]建成一棵二叉树，返回树根
int build(int L1,int R1,int L2,int R2){
	if(L1>R1) return 0;	// empty tree
	int root=post_order[R2];
	int p=L1;
	while(in_order[p]!=root) p++;
	int cnt=p-L1;	// number of nodes on left subtree
	lch[root]=build(L1,p-1,L2,L2+cnt-1);
	rch[root]=build(p+1,R1,L2+cnt,R2-1);
	return root;
}

int best,best_sum;	// current best solution, and best sum

void dfs(int u,int sum){
	sum+=u;
	if(!lch[u]&&!rch[u]){	// leaf, no more nodes
		if(sum<best_sum||(sum==best_sum&&u<best)){best=u;best_sum=sum;}
	}
	if(lch[u]) dfs(lch[u],sum);
	if(rch[u]) dfs(rch[u],sum);
}

int main(){
	while(read_list(in_order)){
		read_list(post_order);
		build(0,n-1,0,n-1);
		best_sum=1000000000;
		dfs(post_order[n-1],0);	// start dfs from root
		cout<<best<<"\n";
	}
	return 0;
}