题目大意：对n个数依次插入建立二叉排序树，输出其中序遍历（数值相同编号小的先输出）以及最大路径长度。

题目描述

输入

输出

样例输入

6
1 3 5 2 3 4

样例输出

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

提示

解题思路

逐个点插入到二叉排序树中，最后输出其中序遍历。

建树：比根小的放左边，比根大的放右边。由于要求稳定排序，需要考虑相等的情况。中序遍历，访问顺序是左子树→根→右子树，如果出现相同的，后插入的要晚输出、后遍历，因此相等时也要放在右边。

最后考虑路径长度，再建树时或者输出中序遍历时，都可以建立最大路径长度。

程序实现

代码二：先读入数据，再进行链表操作，好理解。