描述

给定一个1到n的排列，按顺序依次插入到一棵二叉排序树中，请你将这棵二叉树前序遍历和后序遍历输出。

输入

第一行一个整数n。

接下来一行表示为n个整数，代表1到n的一个排列。

输出

输出所建成的二叉树的前序遍历和后序遍历。

输入样例

10（10个整数）

输出样例

2 1 6 3 5 4 9 7 8 10（前序）
1 4 5 3 8 7 10 9 6 2（后序）

提示

[二叉树的操作基本都是递归操作，只要想想如何在一个节点上判断是朝着左孩子走还是朝着右孩子走就行了。]

简要题意

给定一个1到n（1 ≤ n ≤ 100000）的排列，依次插入到一棵二叉排序树中，求前序遍历和后序遍历。

保证树高不超过50

问题分析

• 二叉排序树

左节点<根节点<右节点

树高不超过50：每次插入一个元素时，不会在二叉树上走超过50步，插入的时间复杂度为O(50n)

前序遍历=输出自己+输出左字树+输出右子树+递归，时间复杂度O(n)

后序遍历=输出左字树+输出右子树+输出自己+递归，时间复杂度O(n)

具体实现（C++版）

#include <bits/stdc++.h>
using namespace std;
// ================= 代码实现开始 =================
/* 请在这里定义你需要的全局变量 */
const int N = 100005;
//二叉树节点的数据结构
//t：二叉树节点数组
struct node{
int val,l,r;
}t[N];
//整个二叉树的根节点，整个二叉树的大小
int root,cnt;
//在以x为根的树中插入一个数字v
//v:要插入的数字
//x:当前节点，下标
//返回根节点x
int insert(int v, int x){
if(x == 0){
//根节点还不存在，则将x变成根节点
x = ++cnt;
t[x].val = v;
t[x].l = 0;
t[x].r = 0;
return x;
}
//递归插入左右子树，先与根节点比较
if(t[x].val < v)
t[x].r = insert(v,t[x].r);
else
t[x].l = insert(v,t[x].l);
return x;
}
//以x为根的二叉树的前序遍历
//x:当前节点
//ans：存储结果的数组
void dlr(int x, vector<int> &ans){
if(x){
//加入x节点的val到ans中，递归求解左右子树
ans.push_back(t[x].val);
dlr(t[x].l,ans);
dlr(t[x].r,ans);
}
}
//后序遍历
void lrd(int x, vector<int> &ans){
if(x){//if(x!=0)
//递归求解左右子树，加入x节点的val到ans中
lrd(t[x].l,ans);
lrd(t[x].r,ans);
ans.push_back(t[x].val);
}
}
// 给定一个1到n的排列，依次插入到二叉树中，返回前序遍历和后序遍历
// n：如题意
// sequence：给定的排列，大小为n
// 返回值：将要输出的元素依次加入到返回值中
vector<int> getAnswer(int n, vector<int> sequence) {
root = cnt =0;
for(int i=0; i<int(sequence.size());++i)
root = insert(sequence[i],root);
vector<int> ans;
dlr(root,ans);
lrd(root,ans);
return ans;
}