0 #P5360. [Lydsy1805月赛]二叉排序树
[Lydsy1805月赛]二叉排序树
二叉排序树
题目描述
二叉排序树是一棵空树,或者是一棵满足以下性质的二叉树:
- 若左子树非空,左子树中所有节点的值都小于或等于根节点的值。
- 若右子树非空,右子树中所有节点的值都大于或等于根节点的值。
- 左、右子树也都是二叉排序树。
按顺序将 个互不相同的数 插入一棵空二叉排序树。插入 时,从根开始:若当前节点为空,将其值设为 并结束;否则,若 小于当前节点的值,则递归插入左子树,反之递归插入右子树。
打乱一个序列的插入顺序后,可能仍得到完全相同的二叉排序树。例如 与 的结果相同。
给定 ,判断是否存在一个序列,使恰好有 种排列后的插入顺序,得到的树与原顺序插入所得的树完全相同。若存在,请构造一个满足输出要求的序列。
输入格式
从标准输入读入一个正整数 ,满足 。
输出格式
若无解,向标准输出写出一行 -1。
否则,第一行输出正整数 ,满足 ;第二行输出 个互不相同的正整数 ,满足 。
若有多组合法解,可以输出任意一组。
样例
输入
8
输出
5
2 1 4 3 5
解释
对应的八种插入顺序为:
2 1 4 3 5
2 1 4 5 3
2 4 1 3 5
2 4 1 5 3
2 4 3 1 5
2 4 3 5 1
2 4 5 1 3
2 4 5 3 1
鸣谢 Claris 提供原题。
相关
在下列比赛中: