A Cartesian tree is a binary tree constructed from a sequence of distinct numbers. The tree is heap-ordered, and an inorder traversal returns the original sequence. For example, given the sequence { 8, 15, 3, 4, 1, 5, 12, 10, 18, 6 }, the min-heap Cartesian tree is shown by the figure.
Your job is to output the level-order traversal sequence of the min-heap Cartesian tree.
Input Specification:
Each input file contains one test case. Each case starts from giving a positive integer N (≤), and then N distinct numbers in the next line, separated by a space. All the numbers are in the range of int.
Output Specification:
For each test case, print in a line the level-order traversal sequence of the min-heap Cartesian tree. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the beginning or the end of the line.
Sample Input:
10
8 15 3 4 1 5 12 10 18 6
Sample Output:
1 3 5 8 4 6 15 10 12 18题意：
给一个最小堆的中序遍历，求层序遍历。
题解：
也不难，最朴素稳妥的方法就是老老实实建树，老老实实bfs层序遍历。最小堆的叶节点总是小于等于根节点，所以每次都挑出最小的值最为根，然后左子树右子树重复上述过程即可。
AC代码：
#include<bits/stdc++.h> using namespace std; int a[505],b[505]; int n; struct node{ int d; node *left,*right; }; queue<node*>q; vector<int>v; node* build(int l,int r){ if(l>r) return NULL; node *root=new node(); int pos=-1,k=9999999;//找到最小的 for(int i=l;i<=r;i++){ if(k>a[i]){ k=a[i]; pos=i; } } root->d=a[pos]; root->left=build(l,pos-1);//左子树 root->right=build(pos+1,r);//右子树 return root; } int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; node *root=build(1,n);//建树 q.push(root);//bfs层序遍历 while(!q.empty()){ node *tree=q.front(); q.pop(); v.push_back(tree->d); if(tree->left) q.push(tree->left); if(tree->right) q.push(tree->right); } for(int i=0;i<v.size();i++){//输出 cout<<v.at(i); if(i!=v.size()-1) cout<<" "; } return 0; }