最近刷数据结构题库时遇到一个有意思的问题,在中文互联网中查询无果,在外文论坛中获得结论,遂在此记录,以防遗忘。 ## 问题描述 给定一个整数数组。如{5,2,4,1,8,7},我们可以得到的BST结构为: ```cpp 5 / \ 2 8 / \ / 1 4 7 ``` 现在,如果我们的输入更改为 [5 2 8 1 7 4],我们的 BST 结构仍将相同。 以下输入顺序都可以得到相同BST结构。 ```cpp 5 2 8 1 4 7 5 2 8 1 7 4 5 2 8 4 1 7 5 2 8 4 7 1 5 2 8 7 1 4 5 2 8 7 4 1 5 2 1 8 4 7 5 2 1 8 7 4 5 2 1 4 8 7 5 2 4 8 1 7 5 2 4 8 7 1 5 2 4 1 8 7 5 8 2 7 1 4 5 8 2 7 4 1 5 8 2 1 7 4 5 8 2 1 4 7 5 8 2 4 7 1 5 8 2 4 1 7 5 8 7 2 1 4 5 8 7 2 4 1 ``` 那么,给定一个整数数组,如何找到输入数组的不同排列数量,从而产生与原始数组顺序上形成的 BST 相同的 BST? ## 其他提示 在中文互联网中,针对如何找到所有得到相同BST的输入序列的算法是有参考的,但是其计算效率过于缓慢,此算法仅限于找出序列数量,而不输出具体的序列内容。 ## 解决方案 采用递归方式进行计算。 1. 对于叶子节点,返回数字1. 2. 对于仅有1个子节点的非叶子节点,该节点返回子节点拓扑顺序数。 3. 对于具有两个子树大小的子节点的非叶节点 |L|以及 |R|,具有 l 和 r 顺序,或者,该数字等于 `l x r x INT(|L|, |R|)` 其中INT(|L|, |R|) = (|L|+|R|)! / (|L|!x |R|!) ## 计算案例 ```cpp Ord(1) = 1 Ord(4) = 1 Ord(2) = 1 x 1 x INT(1, 1) = 2 其中INT(1, 1) = 2! / 1! = 2 Ord(7) = 1 Ord(8) = Ord(7) = 1 Ord(5) = 1 x 2 x INT(3, 2) = 20 其中INT(2, 3) = 5! / (3! x 2!) ``` ## 公式分析 l x r x INT(|L|, |R|)的来源如下: 1. “l” 对生成左子树的序列进行排序的不同方式。 2. “r” 对生成右子树的序列进行排序的不同方式,以及。 3. INT(|L|, |R|)混合这两个序列的不同方法,即将它们交错。INT(a,b) = (a + b)! / (a! x b!) 因为在 a+b 元素的所有交织中,我们只对元素序列 a 具有固定顺序的元素序列感兴趣,元素序列 b 也是如此,因此需要将 (a + b)! 除以 a!和 b!分别。 关于第三点,可以理解为我们在l x r时已经得到了保持BST不变的序列数量,但是我们需要考虑到l序列和r序列交错的情况。 比如目前l序列为1 2 3,r的序列为4 5 6,那么保持l为1 2 3顺序(即2在1后面,3在2后面,以此为规律穿插4 5 6)且r序列为4 5 6顺序的序列还有很多。 ## 参考文献 [[1] 输出构成某一BST拓扑全部序列的算法代码 (效率慢)](https://gist.github.com/kean/40a1e592a608154b117a0dac48baf25f "[1] 输出构成某一BST拓扑全部序列的算法代码 (效率慢)") [[2] 查找产生相同二叉搜索树的给定整数序列的排列数](https://itecnote.com/tecnote/r-find-number-of-permutations-of-a-given-sequence-of-integers-which-yield-the-same-binary-search-tree/ "[2] 查找产生相同二叉搜索树的给定整数序列的排列数") [[3] 公式相关交流与讨论](https://stackoverflow.com/questions/1701612/find-number-of-permutations-of-a-given-sequence-of-integers-which-yield-the-same "[3] 公式相关交流与讨论") Last modification:January 21, 2024 © Allow specification reprint Support Appreciate the author AliPayWeChat Like If you think my article is useful to you, please feel free to appreciate