【UVA 548】Tree 题解（根据遍历序列还原二叉树）-摩杜云开发者社区

要确定给定二叉树中的叶节点的值，该树是从二叉树的根到任何叶的最小值路径。路径的值是值的总和该路径上的节点数。

输入输入文件将包含二叉树的描述，作为中序遍历和后序遍历该树的序列。程序将从输入文件中读取两行（直到文件结束）。第一个行将包含与树的有序遍历相关的值序列行将包含与树的后序遍历相关联的值序列。所有值将不同，大于零且小于10000。您可以假设没有二叉树大于10000个节点或小于1个节点。输出对于每个树描述，应该输出路径值最小的叶节点的值。在如果多条路径的值最小，则应在终端节点上选择值最小的路径。

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

思路

分别用两个数组存储中序遍历（mid）和后序遍历（post）序列，后序遍历的最后一个元素为根节点d，中序遍历以根节点d为界划分左右子树，中序遍历中查找根节点d，数组下标记为index。

左子树中序遍历起点：mid 左子树后序遍历起点：post 左子树在数组中的长度：len 右子树中序遍历起点：mid + index + 1 右子树后序遍历起点：post + index 右子树在数组中的长度：len - index - 1

当无法再进行划分时，通过比较得到从跟到叶子权值和最小的叶子节点的权值。

AC代码

#include <iostream>
#include <vector>
#include <sstream>
#define AUTHOR "HEX9CF"
using namespace std;

#define MAXN 10005

int mid[MAXN], post[MAXN];
int m = 0;
int leaf;
int d;

int restore(int *mid, int *post, int len, int sum)
{
    if (!len)
    {
        // cout << sum << endl;
        return 1;
    }
    d = *(post + len - 1);
    int index = 0;
    while (mid[index] != d)
    {
        index++;
    }
    sum += d;
    int a, b;
    a = restore(mid, post, index, sum);
    b = restore(mid + index + 1, post + index, len - index - 1, sum);
    if (a & b)
    {
        if (m)
        {
            if (sum < m)
            {
                m = sum;
                leaf = d;
            }
        }
        else
        {
            m = sum;
            leaf = d;
        }
        // cout << d << " " << sum << endl;
    }
    return 0;
}

int read(int x[MAXN])
{
    string str;
    if (!getline(cin, str))
    {
        return 0;
    }
    stringstream ss(str);
    int n;
    int i;
    for (i = 0; ss >> n; i++)
    {
        x[i] = n;
    }
    return i;
}

int main()
{
    while (1)
    {
        int len;
        m = 0;
        len = read(mid);
        if (!len)
        {
            break;
        }
        read(post);
        restore(mid, post, len, 0);
        cout << leaf << endl;
    }
    return 0;
}