PAT(甲级)1099 Build A Binary Search Tree(构建二叉搜索树)

Description

题目大意:给出一个n个节点的二叉搜索树(0~n-1)以及其数值，只有一种方式填入其数值，要求构建二叉搜索树，并且层序遍历输出

Input

n个节点，接下来n行代表第i个节点的左子树节点和右子树节点下标，-1代表NULL，最后一行n个数值代表n个节点的数值

Output

该二叉搜索树的层序遍历

解题思路

算法标签：构建二叉搜索树 已知二叉搜索树的中序遍历是从小到大排序，所以可以先把n个数从小到大排序，按照已知二叉搜索树中序遍历将其key值确定，最后按照层序遍历输出

代码

//TSWorld #include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cstring> #include <cmath> #include <vector> using namespace std; const int N = 105; int number[N]; int tot; vector<int>levels[N]; struct node { int key; int left; int right; }tree[N]; // 中序遍历 void BuildTree(int index) { if(index==-1) return; BuildTree(tree[index].left); tree[index].key = number[tot++]; BuildTree(tree[index].right); } // 层序遍历 void Result(int index,int level) { if(index==-1) return; tot = max(tot,level); levels[level].push_back(tree[index].key); Result(tree[index].left,level+1); Result(tree[index].right,level+1); } int main() { int n = 0,tree_left = 0,tree_right = 0; bool first_print = false; cin>>n; for(int i=0;i<n;i++) { cin>>tree_left>>tree_right; tree[i].left = tree_left; tree[i].right = tree_right; } for(int i=0;i<n;i++) cin>>number[i]; sort(number,number+n); // 构建二叉搜索树 BuildTree(0); // 用来记录最大层数 tot = 0; // 将每一层的数值存储到levels Result(0,0); for(int i = 0;i <= tot;i++) { for(int j = 0;j < levels[i].size();j++) { // 消除末尾多余空格 if(!first_print) { cout<<levels[i][j]; first_print = true; } else cout<<" "<<levels[i][j]; } } return 0; }