36个节点，叶子深度差最多为1，可以组成多少棵二叉搜索树？

Question

我正在关注这个挑战：

可以用 36 个节点制作多少二叉搜索树，使得叶子的深度之差最多为 1？

我是否可以说这也意味着36个节点可以组成多少棵完美平衡的二叉树？

这两个问题的意思一样吗？

Answer 1

我是否可以说这也意味着36个节点可以组成多少棵完美平衡的二叉树？这两个问题的意思一样吗？

是的，因为一旦二叉树的形状固定，就只有一种方法可以用数字1..𝑛来标记节点，这样它也是一个BST。

由于叶子的深度只能相差 1，因此树已尽可能保持平衡。因此，树的高度必须为 ⌊log₂36⌋，即 5。树的顶部 31 个节点形成一个完美二叉树，高度为 4（即 5 层）：

               ┌───────────────○───────────────┐
       ┌───────○───────┐               ┌───────○───────┐ 
   ┌───○───┐       ┌───○───┐       ┌───○───┐       ┌───○───┐   
 ┌─○─┐   ┌─○─┐   ┌─○─┐   ┌─○─┐   ┌─○─┐   ┌─○─┐   ┌─○─┐   ┌─○─┐
 ○   ○   ○   ○   ○   ○   ○   ○   ○   ○   ○   ○   ○   ○   ○   ○

现在还有 5 个节点要附加到树的底部，并且在所描绘的树下方的级别中有 32 个“槽”（空）可以放置它们。例如，这是其中之一：

               ┌───────────────○───────────────┐
       ┌───────○───────┐               ┌───────○───────┐ 
   ┌───○───┐       ┌───○───┐       ┌───○───┐       ┌───○───┐   
 ┌─○─┐   ┌─○─┐   ┌─○─┐   ┌─○─┐   ┌─○─┐   ┌─○─┐   ┌─○─┐   ┌─○─┐
 ○   ○  ┌○   ○   ○   ○┐  ○  ┌○┐  ○   ○  ┌○   ○   ○   ○   ○   ○
        ○             ○     ○ ○         ○

所以我们需要统计有多少种方式，从32种中选择5种，即₃₆𝐶₅，即:

₃₆𝐶₅ = 36！ / (5!31!) = 376992