做题网站推荐: OpenJudge VIJOS UOJ CF JOYOI CODEVS 洛谷 RQNOJ BZOJ POJ HDU 牛客网

本站题目推荐: 高精度 模拟 排序 递推 贪心 递归 搜索 动态规划 数学 图论 数据结构 签到 实名认证 卡评测举报

输入输出 变量类型 顺序结构 选择结构 循环结构 一维数组 NOIP 资源下载


问题 2491. -- 二叉排序树

2491: 二叉排序树

时间限制: 1 Sec  内存限制: 128 MB
提交: 42  解决: 22
[上一题][提交][讨论版][状态][下一题]

题目描述

二叉排序树,其中序遍历就是一个有序序列。如果构建呢?一个一个结点插入到二叉树中,如果数据比当前节点小,就往左边插入,否则往右边插入,这样就保证了左子树的点都比根结点小,右子树的结点都不小于根结点。
现有n个数,请依次插入到二叉树中建立一棵二叉排序树,请将其中序遍历输出来,大小相同的先输出编号小的。最后,把这棵二叉树的最长路径长度输出来。

输入

输入两行:
第一行:n
第二行:n个数,空格分隔

输出

输出n+1行:
第1到n行,每行两个数,即中序遍历的结点值以及原编号
第n+1行:树的最长路径长度

样例输入

6
1 3 5 2 3 4

样例输出

1 1
2 4
3 2
3 5
4 6
5 3
4

提示

n不超过10000,所有数字不超过100000

标签

[上一题][提交][讨论版][状态][下一题]