# The order of a Tree

Problem Description

The shape of a binary search tree is greatly related to the order of keys we insert. To be precisely:
1.  insert a key k to a empty tree, then the tree become a tree with
only one node;
2.  insert a key k to a nonempty tree, if k is less than the root ,insert
it to the left sub-tree;else insert k to the right sub-tree.
We call the order of keys we insert “the order of a tree”,your task is,given a oder of a tree, find the order of a tree with the least lexicographic order that generate 　　　　　　　　　　　　　　　　　　　　      the same tree.Two trees are the same if and only if they have the same shape.

Input

There are multiple test cases in an input file. The first line of each testcase is an integer n(n <= 100,000),represent the number of nodes.The second line has n intergers,k1 to kn,represent the order of a tree.To make if more simple, k1 to kn is a sequence of 1 to n.

Output

One line with n intergers, which are the order of a tree that generate the same tree with the least lexicographic.

Sample Input

4

1 3 4 2

Sample Output

1 3 2 4

```#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int ld[100010],rd[100010],a,num,root,i;
void build(int root,int al)
{
if(al>root)
{
if(rd[root]==-1)
{
rd[root]=al;
//cout<<"al:"<<al<<" r root:"<<root<<endl;
}
else build(rd[root],al);
}
else
{
if(ld[root]==-1)
{
ld[root]=al;
//cout<<"al:"<<al<<" l root:"<<root<<endl;
}
else build(ld[root],al);
}
}

void solve(int root)
{
if(ld[root]!=-1)
{
cout<<" "<<ld[root];
solve(ld[root]);
}
if(rd[root]!=-1)
{
cout<<" "<<rd[root];
solve(rd[root]);
}
else return;
}

int main()
{
while(~scanf("%d",&num))
{
memset(ld,-1,sizeof(ld));
memset(rd,-1,sizeof(rd));
for(i=1;i<=num;i++)
{
scanf("%d",&a);
if(i==1){root=a;}
else build(root,a);
}
cout<<root;
solve(root);
cout<<endl;
}
return 0;
}```

## HDU 5444 Elven Postman 二叉排序树

HDU 5444 题意:给你一棵树的先序遍历,中序遍历默认是1...n,然后q个查询,问根节点到该点的路径(题意挺难懂,还是我太傻逼) 思路:这他妈又是个大水题,可是我还是太傻逼.1000个点的树,居然用标准二叉树结构来存点,,,卧槽想些什么东西.可以用一维数组,left,right直接指向位置就行了,我这里用的是链表.对于读入的序列,生成一个二叉排序树,同时记录一下路径就可以了,后面居然忘了清空path又wa了一发. 1 #include<iostream> 2 #include<cs

## 2015 ACM/ICPC Asia Regional Changchun Online HDU 5444 Elven Postman【二叉排序树的建树和遍历查找】

Elven Postman Time Limit: 1500/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 591    Accepted Submission(s): 329 Problem Description Elves are very peculiar creatures. As we all know, they can live for a very

## HDU——PKU题目分类

HDU 模拟题, 枚举1002 1004 1013 1015 1017 1020 1022 1029 1031 1033 1034 1035 1036 1037 1039 1042 1047 1048 1049 1050 1057 1062 1063 1064 1070 1073 1075 1082 1083 1084 1088 1106 1107 1113 1117 1119 1128 1129 1144 1148 1157 1161 1170 1172 1177 1197 1200 1201