[数据结构与算法]二叉树综合：UVA548 树

题目描述：

输入一个二叉树的中序和后序遍历，请你输出一个叶子节点，该叶子节点到根的数值总和最小，且这个叶子是编号最小的那个。 输入： 您的程序将从输入文件中读取两行(直到文件结尾)。第一行是树的中序遍历值序列,第二行是树的后序遍历值序列。所有值将不同，大于零且小于或等于10000.二叉树的节1<=N<=10000。 输出： 对于每个树描述，您应该输出最小值路径的叶节点的值。存在多路径最小的情况下，您应该选择终端叶子节点上具有最小值的那条路径，且输出那个最小值的终端叶子。

输入样例：

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

输出样例：

1
3
255

解题步骤：

1、存储输入数据：

? ? ? ? 输入的数据每个字符中间有空格，想用for循环将字符逐个输入进数组，却又事先不知道序列中字符的个数；想用getline直接读入一整行，却有很多空格字符。

? ? ? ? 先使用getline把整行的序列存储在一个字符串line中；然后使用stringstream定义一个缓冲区s，并把line拷贝进去；最后，逐个从缓冲区中读出字符，把读出的字符保存到数组中，存储完毕后，数组的下标变量就是数组中有效元素的数量-1。

bool Input(int* arr)    //处理输入数据
{
    n = 0;
    string line;
    if (!getline(cin, line))
    {
        return false;
    }
    stringstream s(line);   
    int c = 0;
    while (s >> c)
    {
        arr[n++] = c;
    }
    return n > 0;
}

2、根据中序后序序列还原创建二叉树：

三步：1、后序找根；2、中序分左右；3、递归还原

int CreateTree(int mid_start, int post_start,int len)   //按下标构建二叉树
{
    if (len <= 0)
    {
        return 0;
    }
    int r = post[post_start + len - 1];    //后序找根
    int loc = 0;
    while (mid[mid_start + loc] != r)
    {
        loc++;
    }                                //中序分左右
    lch[r] = CreateTree(mid_start, post_start, loc);
    rch[r] = CreateTree(mid_start + loc + 1, post_start + loc, len - loc -1);
    return r;
}

3、按题意，找出叶子到根上路径的最小值，输出叶子的值；若有路径最小值对应的不止一个叶子，输出最小叶子的值。

? ? ? ? 条件1同时满足比较条件2的方法：

? ? ? ? ? ? ? ? if（比较条件1 || （满足条件1 && 比较条件2）)

? ? ? ? 记录递归的路径：

? ? ? ? ? ? ? ? ?需要定义一个变量放在函数的参数中，在函数中累加后，递归调用中放入累加后的值；

? ? ? ? 判断叶子：

? ? ? ? ? ? ? ? 即无左孩子又无右孩子

void FindMin(int t, int sum)
{
    sum += t;
    if (!lch[t] && !rch[t])   //找到一个叶子
    {
        if (sum < min_path || (sum == min_path && t < min_data))
        {
            min_path = sum;
            min_data = t;
        }
    }
    if (lch[t])
    {
        FindMin(lch[t], sum);
    }
    if (rch[t])
    {
        FindMin(rch[t], sum);
    }
}

总体代码实现：

#include <bits/stdc++.h>
using namespace std;
#define max_size 10001

int root;
int min_data, min_path;
int n, mid[max_size], post[max_size],lch[max_size], rch[max_size];

bool Input(int* arr)    //处理输入数据
{
    n = 0;
    string line;
    if (!getline(cin, line))
    {
        return false;
    }
    stringstream s(line);   
    int c = 0;
    while (s >> c)
    {
        arr[n++] = c;
    }
    return n > 0;
}

int CreateTree(int mid_start, int post_start,int len)   //按下标构建二叉树
{
    if (len <= 0)
    {
        return 0;
    }
    int r = post[post_start + len - 1];    //后序找根
    int loc = 0;
    while (mid[mid_start + loc] != r)
    {
        loc++;
    }                                //中序分左右
    lch[r] = CreateTree(mid_start, post_start, loc);
    rch[r] = CreateTree(mid_start + loc + 1, post_start + loc, len - loc -1);
    return r;
}

void FindMin(int t, int sum)
{
    sum += t;
    if (!lch[t] && !rch[t])   //找到一个叶子
    {
        if (sum < min_path || (sum == min_path && t < min_data))
        {
            min_path = sum;
            min_data = t;
        }
    }
    if (lch[t])
    {
        FindMin(lch[t], sum);
    }
    if (rch[t])
    {
        FindMin(rch[t], sum);
    }
}

int main()
{
    while (Input(mid))
    {
        Input(post);
        root = CreateTree(0, 0, n);
        min_path = 0x7fffffff;
        FindMin(post[n - 1], 0);
        cout << min_data << endl;
    }

    return 0;
}