[抄题报告][UVA]UVA – 548 Tree – 树

题目地址:

https://cn.vjudge.net/problem/UVA-548

题目描述:

(有道翻译)

Background
背景

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.
在给定的二叉树中,您要确定叶节点的值,它是从二进制树的根到任何叶节点的最不值路径的终端节点。路径的值是沿着这条路径的节点的值的和。

The 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.
输入文件将包含对二叉树的描述,作为树的inorder(中序)和postorder(后序)遍历序列。您的程序将从输入文件读取两行(直到文件结束)。第一行将包含与树的inorder遍历相关联的值序列,第二行将包含与树的postorder遍历相关联的值序列。所有的值都是不同的,大于0,小于10000。您可以假设没有任何二叉树会有超过1万个节点或小于1个节点。

The 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


我的分析

在还未看题解时,我想到了后序遍历的最后一个数字一定是根节点,然后在中序遍历里就可以将树划分为左子树和右子树进行操作了。只是我想不明白结束条件,但事实上在对数组操作的时候,定义的左右两个指针如果右指针小于左指针的情况下,就说明没有节点了。

还有,我很纠结计算叶子节点权值那一块,究竟是从根节点往下走,还是从叶子节点往上走?当然了这也可以看出我对前序遍历那块知识的遗忘。

建树,然后找值,这里通过“找到更小的就改值”的方式,全局变量保存的话,遍历一遍,值肯定就是最小的了。

然后,我看到书上说可以一边建树一边算权值,我也试着稍稍修改了一下,通过了。

代码

一边建树一边计算: