文章目录

题目题目分析代码

题目

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

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

输入格式 共2行。

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

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

输出格式 共2行。

第一行，输出树的深度。

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

详见样例输出。

输入输出样例 输入： 8 1 4 3 9 10 35 2 7 输出 ： deep=5 2 3 7 35 10 9 4 1

题目分析

二叉树的插入，后序遍历 （PS：对指针的使用不是很熟练）

代码

#include <iostream> using namespace std; struct node { int val; struct node *l,*r; }; node *root = NULL; int nowdeep,deep; node* newnode (int v) { node* Node = new node ; Node ->val = v ; Node -> l = Node -> r = NULL ; return Node ; } void add(node *&root,int x) //*& 为了改变root { nowdeep ++; if(root == NULL) { root = newnode(x); deep = max (nowdeep,deep); return; } if(x >= root->val) add(root->r,x); else add(root->l,x); } void print(node *root) { if (root == NULL) return ; print(root -> l) ; print(root -> r) ; cout << root->val << endl; } int main() { std::ios::sync_with_stdio(false); int n,x; cin >> n; while(n--) { nowdeep = 0; cin >>x; add(root,x); } cout <<"deep=" << deep << endl; print(root); return 0; }