求1到n的排列生成高度为n-1的斜树的数量及求解方法

核心定义 #

这里的斜树指由1~n的排列生成的高度为n−1的二叉搜索树（BST）——树的结构为单链，所有节点沿左子树或右子树方向依次延伸，根到最远叶子的路径边数为n−1。

对应排列的数量 #

• n=1时：仅1种排列[1]，对应高度为0的树（符合n−1=0），数量为1。
• n≥2时：仅2种有效排列：
  • 严格递增排列1,2,...,n：每个新元素都是当前已插入元素的最大值，只能放在前一节点的右子树位置，最终生成右斜链BST，高度为n−1。
  • 严格递减排列n,n-1,...,1：每个新元素都是当前已插入元素的最小值，只能放在前一节点的左子树位置，最终生成左斜链BST，高度为n−1。

用排列公式推导 #

• n个元素的全排列总数为n!。
• 严格递增排列是全排列中唯一满足“每个元素大于之前所有元素”的序列，数量为n! / n! = 1（元素顺序完全固定，无其他变体）。
• 严格递减排列是全排列中唯一满足“每个元素小于之前所有元素”的序列，数量同样为1。
• 两者求和，总排列数为1+1=2（n≥2）；n=1时直接为1。

内容的提问来源于stack exchange，提问作者chaNcharge