众所周知,二叉查找树的形态和键值的插入顺序密切相关。准确的讲:
我们将一棵二叉查找树的键值插入序列称为树的生成序列,现给出一个生成序列,求与其生成同样二叉查找树的所有生成序列中字典序最小的那个,其中,字典序关系是指对两个长度同为 的生成序列,先比较第一个插入键值,再比较第二个,依此类推。
第一行,一个整数 ,表示二叉查找树的结点个数。第二行,有 个正整数 ,表示生成序列,简单起见, 为一个 到 的排列。
一行, 个正整数,为能够生成同样二叉查找树的所有生成序列中最小的。
4 1 3 4 2
1 3 2 4