P2171 Hz吐泡泡 题解

传送门

题目背景

Hz大大是一种可爱的动物（神）。他很喜欢吐泡泡（更喜欢写作业）。

题目描述

这天，Hz大大心血来潮，吐了n个不同的泡泡玩（保证没有重复的泡泡）。因为他还要写作业，所以他请你帮他把这些泡泡排序成树（左子树<=根<右子树）。输出它的后序遍历。

输入格式

共2行。

第一行，1个整数n。(1<=n<=300000)

第二行，n个数，代表泡泡的大小。

输出格式

共2行。

第一行，输出树的深度。

第二行，输出数的后序遍历。

详见样例输出。

输入输出样例

输入 #1复制

8

1 4 3 9 10 35 2 7

输出 #1复制

deep=5

2

3

7

35

10

9

4

1

说明/提示

水题一道。

题意分析

本题就是一般的二叉搜索树的建立，及二叉树的后序遍历，及求树的深度。

#include<iostream>
using namespace std;
const int maxn=300009;
int n,idx,rt,dep,maxdep=1;
int t[maxn];
int ch[maxn][2]; 
void insert(int &x,int val)
{
	if (!x)
	{
		x=++idx;
		t[x]=val;
		return ;
	}
	else
	{
		dep++;
		if (val<t[x]) insert(ch[x][0],val);
		else insert(ch[x][1],val);
	}
}
void order(int x)
{
	if (!x) return ;
	order(ch[x][0]);
	order(ch[x][1]);
	cout<<t[x]<<"\n";
}
int main()
{
	int n;
	cin>>n;
	for (int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		dep=1;
		insert(rt,x); 
		maxdep=max(maxdep,dep);
	}
	cout<<"deep="<<maxdep<<endl;
	order(rt);
}