Uva548-二叉树构建&&DFS

发表于 | 分类于 ， | | 阅读次数:

首先根据二叉树的中序和后序遍历构建二叉树，然后找一个叶子节点使得它到根的路径上的权和最小。

链接

Uva548-Tree

题目描述

给一棵点带权（权值各不相同，都是小于10000的正整数）的二叉树的中序和后序遍历，找一个叶子节点使得它到根的路径上的权和最小。如果有多解，该叶子本身的权应尽量小。输入中每两行表示一棵树，其中第一行为中序遍历，第二行为后序遍历。

题解

根据中序和后序遍历可以构建出这棵二叉，然后用DFS搜索找到结果。

代码

通过设置best_sum和best找到最优解的方法值得学习啊。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/*
 *
 * Author : Aincrad
 *
 * Date : Sat 22 Sep 11:20:12 CST 2018
 *
 */
 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e4 + 7;
int in_order[maxn], post_order[maxn], lch[maxn], rch[maxn];
string line;
int n;
int best, best_sum;

bool read(int* s){
    if(!getline(cin, line)) return false;
    stringstream ss(line);
    n = 0;
    int x;
    while(ss >> x){
        s[n++] = x;
    }
    return true;
}

int build(int l1, int r1, int l2, int r2){
    if(l1 > r1) return 0;
    int v = post_order[r2];
    int pos = 0;
    while(in_order[pos] != v) pos++;
    int len = pos - l1;
    lch[v] = build(l1, l1 + len - 1, l2, l2 + len - 1);
    rch[v] = build(l1 + len + 1, r1, l2 + len, r2 - 1);
    return v;
}

void dfs(int v, int sum){
    sum += v;
    if(!lch[v] && !rch[v]){
        if(sum < best_sum || (sum == best_sum && v < best)){
            best_sum = sum;
            best = v;
        }
        return;
    }
    if(lch[v]) dfs(lch[v], sum);
    if(rch[v]) dfs(rch[v], sum);
}

int main(){
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
    #endif
    
    while(read(in_order)){
        read(post_order);
        int root = build(0, n - 1, 0, n - 1);
        best_sum = 1e9;
        dfs(root, 0);
        cout << best << endl;
    }
    
    return 0;
}