1.这道题目难度不大，根据给出的数组和BST二叉树，进行填值，主要思想如下：
1）先构建二叉树（此时尚未填值）；
2）输出二叉树的中序遍历地址；
3）对数组进行排序；
4）把数组的数输入到中序遍历地址相应的节点值中。
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.
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
AC代码：
[c language=”++”]
//#include<string>
//#include <iomanip>
#include<vector>
#include <algorithm>
//#include<stack>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
using namespace std;
struct TreeNode{
int val;
TreeNode*left, *right;
TreeNode(int x) :val(x), left(NULL), right(NULL){};
TreeNode() :val(-1), left(NULL), right(NULL){};
};
void inOrder(TreeNode*root,vector<TreeNode*>&in)
{
if (root != NULL)
{
inOrder(root->left, in);
in.push_back(root);
inOrder(root->right, in);
}
}
int main(void)
{
int n;
cin >> n;
if (n == 0) return 0;
TreeNode *tree = new TreeNode[n];
//建立二叉树
for (int i = 0; i < n; i++)
{
int a, b;
scanf("%d %d", &a, &b);
if (a != -1)
tree[i].left = &tree[a];
if (b != -1)
tree[i].right = &tree[b];
}
//读取数组
vector<int> num(n, 0);
for (int i = 0; i < n; i++)
{
scanf("%d", &num[i]);
}
//数组排序
sort(num.begin(), num.end());
//建立中序遍历数组
vector<TreeNode*> treeAddress(0);
inOrder(&tree[0], treeAddress);
for (int i = 0; i < n; i++)
{
treeAddress[i]->val = num[i];
}
//进行层序遍历
queue<TreeNode*> q;
int count1 = 0;
int count2 = 0;
if (num.size() != 0)
{
q.push(&tree[0]);
count1++;
}
vector<int> outPut(0);
while (!q.empty())
{
for (int i = 0; i < count1; i++)
{
TreeNode* tmp = q.front(); q.pop();
outPut.push_back(tmp->val);
if (tmp->left != NULL)
{
q.push(tmp->left);
count2++;
}
if (tmp->right != NULL)
{
q.push(tmp->right);
count2++;
}
}
count1 = count2;
count2 = 0;
}
//输出结果
for (int i = 0; i < outPut.size(); i++)
{
cout << outPut[i];
if (i != outPut.size() – 1)
cout << " ";
}
cout << endl;
return 0;
}
[/c]