UVA 548 Tree 二叉树的中序后序遍历构造树

　　题目链接： UVA 548

　　题目描述：给出一棵树的中序遍历和后序遍历，输出权值和最小的叶子节点值，若相等则输出叶子节点权值最小的

　　解题思路：就是纯的对树的中序遍历和后序遍历的理解问题

　　代码：

#include <iostream>
#include <queue>
#include <string>
#include <vector>
#include <algorithm>
#include <list>
#include <iterator>
#include <cmath>
#include <cstring>
#include <forward_list>
#include <sstream>
using namespace std;

const int maxn = 1e5 + 10;
const int INF = 0x3fffffff;
int in_order[maxn], post_order[maxn], lch[maxn], rch[maxn];
int n;

bool read_list(int *a) {
    string line;
    if(!getline(cin, line)) return false;
    stringstream ss(line);
    int x;
    n = 0;
    while(ss >> x) {
        a[n++] = x;
    }
    return n > 0;
}
// in_order[L1~R1], post_order[L2~R2]
int build(int L1, int R1, int L2, int R2) {
    if(L1 > R1 || L2 > R2) return 0;
    int root = post_order[R2];
    int p = L1;
    //printf("%d %d %d %d
", L1,R1,L2,R2);
    while(in_order[p] != root) {
        p++;
    }
    int cnt = p-L1;
    lch[root] = build(L1, L1+cnt-1, L2, L2+cnt-1);
    rch[root] = build(p+1, R1, L2+cnt, R2-1);
    return root;
}

int best_res, best_sum;

void dfs(int u, int sum) {
    sum += u;
    if(!lch[u] && !rch[u]) {
        if(sum < best_sum && u < best_res) {
            best_res = u;
            best_sum = sum;        
        }
    }
    if(lch[u]) dfs(lch[u], sum);
    if(rch[u]) dfs(rch[u], sum);
}

int main() {
    freopen("in.txt", "r", stdin);
    while(read_list(in_order)) {
        memset(lch, 0, sizeof(lch));
        memset(rch, 0, sizeof(rch));
        read_list(post_order);
        /*for(int i = 0; i < n; i++) {
            cout << in_order[i] << " ";
        }
        cout << endl;
        for(int i = 0; i < n; i++) {
            cout << post_order[i] << " ";
        }
        cout << endl;*/
        best_sum = best_res = INF;
        build(0,n-1,0,n-1);
        cout << "build is done" << endl;
        dfs(post_order[n-1], 0);
        cout << best_res << endl;
    }    
    return 0;
}

View Code

　　思考：中间踩了不少坑，比如best_res 我初始化为-1了这个很快我就找出来了，可是一开始build的时候函数传参错了，画了10分钟才找出来，这是我的锅，但是总体来讲收获还是很大的，比如学会了stringstream , 这个其实就是sscanf的C++版，还好还好，感觉不错，加油备战EC，现在比赛感觉心态已经很正了，毕竟打铁已成家常