HDU 3999 二叉排序树

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;
}

时间: 12-21

HDU 3999 二叉排序树的相关文章

hdu 3999 The order of a Tree

题目连接 http://acm.hdu.edu.cn/showproblem.php?pid=3999 The order of a Tree Description As we know,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 beco

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

HDU 6203 ping ping ping [LCA,贪心,DFS序,BIT(树状数组)]

题目链接:[http://acm.hdu.edu.cn/showproblem.php?pid=6203] 题意 :给出一棵树,如果(a,b)路径上有坏点,那么(a,b)之间不联通,给出一些不联通的点对,然后判断最少有多少个坏点. 题解 :求每个点对的LCA,然后根据LCA的深度排序.从LCA最深的点对开始,如果a或者b点已经有点被标记了,那么continue,否者标记(a,b)LCA的子树每个顶点加1. #include<Bits/stdc++.h> using namespace std;

HDU 5542 The Battle of Chibi dp+树状数组

题目:http://acm.hdu.edu.cn/showproblem.php?pid=5542 题意:给你n个数,求其中上升子序列长度为m的个数 可以考虑用dp[i][j]表示以a[i]结尾的长度为j的上升子序列有多少 裸的dp是o(n2m) 所以需要优化 我们可以发现dp的第3维是找比它小的数,那么就可以用树状数组来找 这样就可以降低复杂度 #include<iostream> #include<cstdio> #include<cstring> #include

hdu 1207 汉诺塔II (DP+递推)

汉诺塔II Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 4529    Accepted Submission(s): 2231 Problem Description 经典的汉诺塔问题经常作为一个递归的经典例题存在.可能有人并不知道汉诺塔问题的典故.汉诺塔来源于印度传说的一个故事,上帝创造世界时作了三根金刚石柱子,在一根柱子上从下往

[hdu 2102]bfs+注意INF

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2102 感觉这个题非常水,结果一直WA,最后发现居然是0x3f3f3f3f不够大导致的--把INF改成INF+INF就过了. #include<bits/stdc++.h> using namespace std; bool vis[2][15][15]; char s[2][15][15]; const int INF=0x3f3f3f3f; const int fx[]={0,0,1,-1};

HDU 3555 Bomb (数位DP)

数位dp,主要用来解决统计满足某类特殊关系或有某些特点的区间内的数的个数,它是按位来进行计数统计的,可以保存子状态,速度较快.数位dp做多了后,套路基本上都差不多,关键把要保存的状态给抽象出来,保存下来. 简介: 顾名思义,所谓的数位DP就是按照数字的个,十,百,千--位数进行的DP.数位DP的题目有着非常明显的性质: 询问[l,r]的区间内,有多少的数字满足某个性质 做法根据前缀和的思想,求出[0,l-1]和[0,r]中满足性质的数的个数,然后相减即可. 算法核心: 关于数位DP,貌似写法还是