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.
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIyZwpmL2UzNwMzN0IDM4AjMxkTMwIzLc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.jpg)
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 (≤30), 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
思路&分析
給出了一組樹的
inorder traversal
中序周遊結果,用最小堆的形式建樹。因為中序周遊根節點在中間,最小堆的根節點最小,那麼每次從序列中找到最小值就是根,左半部分為左子樹,右半部分為右子樹,遞歸建樹即可。最後根據題目要求用隊列輸出層次周遊結果。
注意點:
感覺沒什麼注意點…雖然是最後一題,但确是通過率最高的一題(通過率與分值成正比 :smile)建樹基本功。
送出代碼(AC)
#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
#define INF 0x3fffffff
using namespace std;
int in[40];
struct node{
int data;
node *left,*right;
};
node * create(int lnum,int rnum){
if(lnum>rnum) return NULL;
int k=lnum,MIN=INF;
for(int i=lnum;i<=rnum;i++){
if(in[i]<MIN){
k=i;MIN=in[i];
}
}
node *root=new node();
root->data=in[k];
root->left=create(lnum,k-1);
root->right=create(k+1,rnum);
return root;
}
int main()
{
// freopen("1.txt","r",stdin);
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>in[i];
}
node * root=create(1,n);
vector<int> res;
queue<node *> q;
q.push(root);
while(!q.empty()){
node *f=q.front();
q.pop();
res.push_back(f->data);
if(f->left) q.push(f->left);
if(f->right) q.push(f->right);
}
for(int i=0;i<res.size();i++){
cout<<res[i];
if(i!=res.size()-1) cout<<" ";
}
return 0;
}