UVA 548 Tree(二叉树的前序，中序，后序遍历）

​​UVA 548​​

题意

每组输入给你一颗二叉树的中序，后序遍历结果，各占一行。让你求出根节点到叶子路径的最小权值（路径相同取叶子节点小的）例如：

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

分析

1. 首先说下二叉树的三种遍历方式（先序，中序，后序），都是递归定义的

先序： = + +

中序： = + +

后序： = + +

2. 这道题给出中序和后序，那么就可以构建出二叉树，具体做法根据后序序列找根节点，因为根据上面式子可以看出来，根节点就在最后。然后根据中序序列找左右节点的数量（根节点左边就是左子树节点的数量），递归循环即可。

3. 最后把树建好后，dfs先序遍历找最小权值路径。

#include<bits/stdc++.h>
using namespace std;
const int N = 10000 + 10;
const int INF = 0x3f3f3f3f;
int in_order[N], post_order[N];
int lch[N], rch[N];
int n;                      //节点个数
int ans, ans_sum;           //最优叶子节点， 对应的权值
bool input(int* a)          //读入一行           
{
    string line;
    if(!getline(cin, line))
        return false;       //文件结束
    stringstream ss(line);
    n = 0;
    int num;
    while(ss >> num)
        a[n++] = num;
    return n > 0;
}
int bulid(int L1, int R1, int L2, int R2)       //递归建树  in_order[L1---R2]
{                                               //          post_order[L2, R2]
    if(L1 > R1)
        return 0;                      //空树
    int root = post_order[R2];
    int p = L1;                        //p为根节点
    while(in_order[p] != root)
        p++;                        //找到根节点在中序的位置
    int cnt = p - L1;               //左子树的节点个数
    lch[root] = bulid(L1, p - 1, L2, L2 + cnt - 1);      
    rch[root] = bulid(p + 1, R1, L2 + cnt, R2 - 1);
    return root;
}

void dfs(int u, int sum)
{
    sum += u;
    if(!lch[u] && !rch[u])  //叶子
    {
        //当前路径权值较小，或路径权值相同但叶子节点较小，更新
        if(sum < ans_sum || (sum == ans_sum && u < ans)){   
            ans = u;
            ans_sum = sum;
        }
    }
    if(lch[u])              //对左右子树递归
        dfs(lch[u], sum);
    if(rch[u])
        dfs(rch[u], sum);
}

int main()
{
    while(input(in_order)){
        input(post_order);          //分别读入中序，和后序遍历
        bulid(0, n-1, 0, n-1);      //建树
        ans_sum = INF;
        dfs(post_order[n - 1], 0);   //遍历
        cout << ans << endl;
    }
    return 0;
}