题目描述
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;
}
