[数据结构与算法]PATA1099_中序建树（难度：????）

这个题又是虚晃一枪，看似要用BST建树仔细一读题其实中序遍历足以。
考点：

1、没访问过的是root。

2、中序遍历。

3、层次遍历。

#include <bits/stdc++.h>
using namespace std;
int pos = 0;
bool vis[120];
vector<int> v, ans;
struct node {
    int val;
    int lc, rc;
}tree[120];
void inorder(int root) {
    if (root == -1) return;
    inorder (tree[root].lc);
    tree[root].val = v[pos++];
    inorder (tree[root].rc);
}
int main() {
    int n, lc, rc, root;
    scanf ("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf ("%d %d", &lc, &rc);
        tree[i].lc = lc;
        tree[i].rc = rc;
        if (lc != -1) vis[lc] = true;
        if (rc != -1) vis[rc] = true;
    }
    v.resize(n);
    for (int i = 0; i < n; i++) {
        scanf ("%d", &v[i]);
        if (vis[i] == false) root = i;
    }
    sort (v.begin(), v.end());
    inorder (root);
    queue<int> q;
    q.push(root);
    while (!q.empty()) {
        int now = q.front();
        ans.push_back(tree[now].val);
        q.pop();
        if (tree[now].lc != -1) q.push(tree[now].lc);
        if (tree[now].rc != -1) q.push(tree[now].rc);
    }
    for (int i = 0; i < ans.size(); i++) {
        if (i != 0) printf (" ");
        printf ("%d", ans[i]);
    }
}