Uva--548 Tree(三个递归遍历/重建二叉树)

记录
23:13 2023-5-18

uva.onlinejudge.org/external/5/548.html

reference:《算法竞赛入门经典第二版》例题6-8

使用中序遍历和后序遍历还原二叉树，还行，还是熟悉的。
收获的点:

1. 使用数组快速建立二叉树(还是要变通，《数据结构与算法分析》中标准的使用了结构体指针，太过学术了？
2. 函数中参数作为中间变量传递，这样就可以不用修改了，栈退去后值也相当于回来了(下面preorder1和preorder的区别)(这个我居然忘了。。。

#include<cstdio>
#include<iostream>
#include<sstream>
#define MAX_N 10000
using namespace std;
typedef long long ll;
typedef unsigned int uint;
const int INF = 0x3f3f3f3f;

int ind = 0;
int inorder[MAX_N + 1], postorder[MAX_N + 1], le[MAX_N + 1], ri[MAX_N + 1];
int sum = INF;
int temp = 0;
int result = 0;

bool read_list(int* a) {
  string line;
  if(!getline(cin, line)) return false;
  stringstream ss(line);
  ind = 0;
  int x;
  while(ss >> x) a[ind++] = x;
  return ind > 0;
}

// inorder [l1 r1]
// postorder [l2 r2]
int build_tree(int l1, int r1, int l2, int r2) {
    if(l1 > r1) return 0;
    int root = postorder[r2];
    for(int i = l1; i <= r1; i++) {
        if(root == inorder[i]) {
            int l = build_tree(l1, i - 1, l2, l2 + i - 1 - l1);
            int r = build_tree(i + 1, r1, l2 + i - l1, r2 - 1);
            le[root] = l;
            ri[root] = r;
            break;
        }
    }
    return root;
}

void preorder(int root) {
    temp += root;
    if(le[root] == 0 && ri[root] == 0) {
        if(temp < sum || (temp == sum && root < result)) {
            sum = temp;
            result = root;
        }
        temp -= root;
        return;
    }
    if(le[root]) {
        preorder(le[root]);
    }
    if(ri[root]) { 
        preorder(ri[root]);
    }
    temp -= root;
}

void preorder1(int root, int temp) {
    temp += root;
    if(le[root] == 0 && ri[root] == 0) {
        if(temp < sum || (temp == sum && root < result)) {
            sum = temp;
            result = root;
        }
        return;
    }
    if(le[root]) {
        preorder1(le[root], temp);
    }
    if(ri[root]) { 
        preorder1(ri[root], temp);
    }
}

void solve() {
    sum = INF;
    temp = 0;
    result = 0;
    build_tree(0, ind-1, 0, ind-1);
    preorder1(postorder[ind-1], 0);
    printf("%d\n", result);
}

int main() {
    while (read_list(inorder)) {
        read_list(postorder);
        solve();
    }
    return 0;
}