题目描述

A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
Both the left and right subtrees must also be binary search trees.

Given the structure of a binary tree and a sequence of distinct integer keys, there is only one way to fill these keys into the tree so that the resulting tree satisfies the definition of a BST. You are supposed to output the level order traversal sequence of that tree. The sample is illustrated by Figure 1 and 2.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤100) which is the total number of nodes in the tree. The next N lines each contains the left and the right children of a node in the format left_index right_index, provided that the nodes are numbered from 0 to N−1, and 0 is always the root. If one child is missing, then −1 will represent the NULL child pointer. Finally N distinct integer keys are given in the last line.

Output Specification:

For each test case, print in one line the level order traversal sequence of that tree. All the numbers must be separated by a space, with no extra space at the end of the line.

Sample Input:

9
1 6
2 3
-1 -1
-1 4
5 -1
-1 -1
7 -1
-1 8
-1 -1
73 45 11 58 82 25 67 38 42

Sample Output:

58 25 82 11 38 67 45 73 42

考点

1.二叉树搜索；
2.遍历。

思路

1.我的思路（复杂）
首先根据输入构造二叉搜索树的结构，然后遍历出每个结点的左右子树所包含结点的个数。然后将输入的数组进行排序，根据左右子孙数便可定位每个结点应该放什么值。
2.柳神的思路
二叉搜索树中序遍历的结果就是由小到大排列的，因此将数组排序之后方可一一对应。
3.小结
我想的实在是有点复杂，归根究底应该是对二叉搜索树的性质不够熟悉。其中，对于输入的结点的排序，我和柳神都使用了c++中的sort函数。注意需要引入头文件#include <algorithm>。

代码

1.我的代码（复杂版）

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct node {
    int val;
    int left, right;
    int lnum, rnum;
};
vector<node> bt;
vector<int> sq;
queue<int> q;
int n, c=0;
int calculate(int k) {
    if (bt[k].left == -1 && bt[k].right == -1) return 1;
    if (bt[k].left != -1) bt[k].lnum = calculate(bt[k].left);
    if (bt[k].right != -1) bt[k].rnum = calculate(bt[k].right);
    return bt[k].lnum + bt[k].rnum + 1;
}
void buildTree(int s, int e, int k) {
    if (s > e) return;
    bt[k].val = sq[s + bt[k].lnum];
    if (s == e)return;
    int t1 = s + bt[k].lnum - 1;
    if (bt[k].left != -1) buildTree(s, s + bt[k].lnum - 1, bt[k].left);
    if (bt[k].right != -1) buildTree(s+ bt[k].lnum + 1, e, bt[k].right);
}
void levelorder() {
    while (!q.empty()) {
        int t = q.front();
        c++; cout << bt[t].val << (c != n ? " " : "\n");
        q.pop();
        if (bt[t].left != -1)q.push(bt[t].left);
        if (bt[t].right != -1)q.push(bt[t].right);
    }
}
int main() {
    int i;
    cin >> n;
    bt.resize(n); sq.resize(n);
    for (i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        bt[i].left = a;
        bt[i].right = b;
        bt[i].lnum = 0;
        bt[i].rnum = 0;
    }
    for (i = 0; i < n; i++) {
        cin >> sq[i];
    }
    calculate(0);
    sort(sq.begin(), sq.end());
    buildTree(0, n-1, 0);
    q.push(0);
    levelorder();
    return 0;
}

2.完善版

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct node {
    int val;
    int left, right;
};
vector<node> bt;
vector<int> sq;
queue<int> q;
int n, c=0, t=0;
void inorder(int k) {
    if (bt[k].left == -1 && bt[k].right == -1) {
        bt[k].val = sq[t++];
        return;
    }
    if (bt[k].left != -1)inorder(bt[k].left);
    bt[k].val = sq[t++];
    if (bt[k].right != -1)inorder(bt[k].right);
}
void levelorder() {
    while (!q.empty()) {
        int t = q.front();
        cout << bt[t].val << ((++c) != n ? " " : "\n");
        q.pop();
        if (bt[t].left != -1)q.push(bt[t].left);
        if (bt[t].right != -1)q.push(bt[t].right);
    }
}
int main() {
    int i, a, b;
    cin >> n;
    bt.resize(n); sq.resize(n);
    for (i = 0; i < n; i++) {
        cin >> a >> b;
        bt[i].left = a;
        bt[i].right = b;
    }
    for (i = 0; i < n; i++) cin >> sq[i];
    sort(sq.begin(), sq.end());
    inorder(0);
    q.push(0);
    levelorder();
    return 0;
}

1099.Build A Binary Search Tree