UVA - 548 Tree（二叉树的递归遍历）

题意：已知中序后序序列，求一个叶子到根路径上权和最小，如果多解，则叶子权值尽量小。

分析：已知中序后序建树，再dfs求从根到各叶子的权和比较大小

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<cmath>

#include<iostream>

#include<sstream>

#include<iterator>

#include<algorithm>

#include<string>

#include<vector>

#include<set>

#include<map>

#include<stack>

#include<deque>

#include<queue>

#include<list>

typedef long long ll;

typedef unsigned long long llu;

const int INT_INF = 0x3f3f3f3f;

const int INT_M_INF = 0x7f7f7f7f;

const ll LL_INF = 0x3f3f3f3f3f3f3f3f;

const ll LL_M_INF = 0x7f7f7f7f7f7f7f7f;

const int dr[] = {, , -, };

const int dc[] = {-, , , };

const double pi = acos(-1.0);

const double eps = 1e-;

const int MAXN =  + ;

const int MAXT =  + ;

using namespace std;

string a, b;

vector<int> in_order, post_order;

int leftchild[MAXN];

int rightchild[MAXN];

int anssum;

int ansv;

int build_tree(int L1, int R1, int L2, int R2){

    if(L1 > R1) return ;

    int root = post_order[R2];

    int st = L1;

    while(in_order[st] != root) ++st;

    int cnt = st - L1;//一定要通过个数来控制取出来的中序后序序列的左右下标

    leftchild[root] = build_tree(L1, st - , L2, L2 + cnt - );//值为root的左孩子结点的值,第四个参数不能写成st-1，因为取出来的相对应的中序和后序序列不一定是下标对齐的

    rightchild[root] = build_tree(st + , R1, L2 + cnt, R2 - );

    return root;

}

void dfs(int root, int sum){

    sum += root;

    if(!leftchild[root] && !rightchild[root]){//叶子

        if(sum < anssum || (sum == anssum && root < ansv)){

            anssum = sum;

            ansv = root;

        }

    }

    if(leftchild[root]){

        dfs(leftchild[root], sum);

    }

    if(rightchild[root]){

        dfs(rightchild[root], sum);

    }

}

int main(){

    while(getline(cin, a)){

        in_order.clear();

        post_order.clear();

        memset(leftchild, , sizeof leftchild);

        memset(rightchild, , sizeof rightchild);

        stringstream s1(a);

        int x;

        while(s1 >> x){

            in_order.push_back(x);

        }

        getline(cin, b);

        stringstream s2(b);

        while(s2 >> x){

            post_order.push_back(x);

        }

        int len = in_order.size();

        build_tree(, len - , , len - );

        int root = post_order[len - ];

        anssum = INT_M_INF;

        ansv = INT_M_INF;

        dfs(root, );

        printf("%d\n", ansv);

    }

}

已知中序和后序可建树，建成后，可输出前序序列。

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<cmath>

#include<iostream>

#include<sstream>

#include<iterator>

#include<algorithm>

#include<string>

#include<vector>

#include<set>

#include<map>

#include<stack>

#include<deque>

#include<queue>

#include<list>

typedef long long ll;

typedef unsigned long long llu;

const int INT_INF = 0x3f3f3f3f;

const int INT_M_INF = 0x7f7f7f7f;

const ll LL_INF = 0x3f3f3f3f3f3f3f3f;

const ll LL_M_INF = 0x7f7f7f7f7f7f7f7f;

const int dr[] = {, , -, };

const int dc[] = {-, , , };

const double pi = acos(-1.0);

const double eps = 1e-;

const int MAXN =  + ;

const int MAXT =  + ;

using namespace std;

string a, b;

vector<int> in_order, post_order, pre_order;

int leftchild[MAXN];

int rightchild[MAXN];

int build_tree(int L1, int R1, int L2, int R2){

    if(L1 > R1) return ;

    int root = post_order[R2];

    int st = L1;

    while(in_order[st] != root) ++st;

    int cnt = st - L1;//一定要通过个数来控制取出来的中序后序序列的左右下标

    leftchild[root] = build_tree(L1, st - , L2, L2 + cnt - );//值为root的左孩子结点的值,第四个参数不能写成st-1，因为取出来的相对应的中序和后序序列不一定是下标对齐的

    rightchild[root] = build_tree(st + , R1, L2 + cnt, R2 - );

    return root;

}

void dfs(int root){

    pre_order.push_back(root);

    if(leftchild[root]){

        dfs(leftchild[root]);

    }

    if(rightchild[root]){

        dfs(rightchild[root]);

    }

}

int main(){

    while(getline(cin, a)){

        in_order.clear();

        post_order.clear();

        pre_order.clear();

        memset(leftchild, , sizeof leftchild);

        memset(rightchild, , sizeof rightchild);

        stringstream s1(a);

        int x;

        while(s1 >> x){

            in_order.push_back(x);

        }

        getline(cin, b);

        stringstream s2(b);

        while(s2 >> x){

            post_order.push_back(x);

        }

        int len = in_order.size();

        build_tree(, len - , , len - );

        int root = post_order[len - ];

        dfs(root);

        for(int i = ; i < len; ++i){

            if(i) printf(" ");

            printf("%d", pre_order[i]);

        }

        printf("\n");

    }

}