【紫书】Tree UVA - 548 静态建树dfs

题意：给你中序后序求某叶子节点使得从根到该节点权值和最小。若存在多个，输出其权值最小的那个。

题解：先建树，然后暴力dfs/bfs所有路径，取min

技巧：递归传参数，l1,r1,l2,r2, sum,root,

代码：

#define _CRT_SECURE_NO_WARNINGS

#include "stdio.h"

#include<stdio.h>

#include<algorithm>

#include<string>

#include<vector>

#include<list>

#include<set>

#include<iostream>

#include<string.h>

#include<queue>

#include<string>

#include<sstream>

using namespace std;

const int maxn = 1e4+;

string line; int n;

int a[maxn],in_order[maxn],post_order[maxn];

int lch[maxn], rch[maxn];

int mn,best;

bool read_list(int *a) {

    if (!getline(cin, line)) return false;

    stringstream ss(line);

     n = ;

    int x;

    while (ss >> x)a[n++] = x;

    return n > ;

}

int  build(int l1, int r1, int l2, int r2) {//将中序l1,r1 将后序l2,r2 建成一棵树，返回树根

    if (l1 > r1)return ;

    int root = post_order[r2];

    int p = l1;

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

    int cnt = p - l1;

    lch[root] = build(l1, p - , l2, l2 + cnt - );

    rch[root] = build(p + , r1, l2 + cnt, r2 - );

    return root;

}

void dfs(int u, int sum) {

    sum += u;

    if (!lch[u] && !rch[u]) if (sum < mn || (sum == mn&&u < best)) {best = u; mn = sum;}

    if (lch[u])dfs(lch[u], sum);

    if (rch[u])dfs(rch[u], sum);

}

int main() {

    while (read_list(in_order)) {

        read_list(post_order);

        build(, n - , , n - );

        mn = 1e9;

        dfs(post_order[n - ], );

        cout << best << "\n";

    }

    //system("pause");

}