[C++知识库]***1068. 最小权值路径

题目：

代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define maxn 11111
char s1[maxn], s2[maxn];
int in[maxn], post[maxn];	// 中序和后序
const int INF =0x3f3f3f3f;
struct node 
{		// 二叉树结点
	int data;		// 数据域
	node* left;		// 左孩子
	node* right;	// 右孩子
};

node* build(int* in, int* post, int il, int ih, int pl, int ph) 
{// 根据中序遍历in[il, ih]和后序遍历post[pl, ph]构造二叉树
	if(il>ih) 
    {	// 空树
		return NULL;
	}
	node* root=(node*)malloc(sizeof(node));	// 根节点
	root->data=post[ph];
	// 在中序遍历中寻找根节点，然后划分左右子树
	int rootInd=il;
	while(in[rootInd]!=root->data) rootInd++;
	int llen=rootInd-il;	// 左子树的长度
	int rlen=ih-rootInd;
	root->left=build(in,post,il,il+llen-1,pl,pl+llen-1);	// 递归构造左子树
	root->right=build(in,post,rootInd+1,ih,pl+llen,ph-1);	// 递归构造右子树
	return root;
}
int getNum(char s[], int len, int a[]) 
{// 将长度为len的字符串解析为整型数组，并返回长度
	int num=0;	// 保存解析的数字
	int ind=0;	// a的下标
	for(int i=0;i<len;i++) 
    {
		if(s[i]==' ') 
        {	// 空格为分割符，当前数字解析完成
			a[ind++]=num;
			num=0;	// 方便解析下一个数字
		}
        else 
        {	// 数字
			num=num*10+s[i]-'0';
		}
	}
	a[ind]=num;
    ind++;	// 保存最后一个数字
	return ind-1;
}

int minPath=INF;
int minnode;
void dfs(node* u, int sum) 
{// 先序遍历二叉树,sum记录当前结点(不包含)到根节点的权值和
	if(u!=NULL) 
    {	// 非空结点
		if(u->right==NULL&&u->left==NULL) 
        {	// 遍历到叶子结点
			if(sum+u->data<minPath||(sum+u->data==minPath&&u->data<minnode)) 
            {	// 找到更“优”叶子结点
				minPath=sum+u->data;
				minnode=u->data;
			}
		}
		dfs(u->left,sum+u->data);	// 递归遍历左子树
		dfs(u->right,sum+u->data);	// 递归遍历右子树
	}
}
int main() 
{
	int numcnt;
	while(gets(s1)&&gets(s2)) 
    { // 接受两行字符串
		getNum(s1,strlen(s1),in);
		numcnt=getNum(s2,strlen(s2),post);
		node* root=build(in,post,0,numcnt,0,numcnt);	// 构造二叉树
		minPath=INF; 	// 每次遍历都有初始化
		minnode=root->data;
		dfs(root,0);
		printf("%d\n",minnode);
	}
	return 0;
}