algorithm - 给定一个数 n，有多少平衡二叉树(不是二叉搜索树)？

Question

本题中balanced的定义是

The number of nodes in its left subtree and the number of nodes in its right subtree are almost equal, which means their difference is not greater than one

如果给定一个 n 作为节点的总数，那么这样的树有多少？

---

另外，如果我们用 height 替换 the number of nodes 会怎样？给定一个高度，有多少棵高度平衡的树？

Answer 1

好吧，差异只会由最后一层造成，因此您可以找到应该为该层保留多少节点，然后考虑所有可能的组合。有 n 个节点，你知道高度应该是 floor(log(n)) 因此同一棵树在深度 k = floor(log(n)) - 1 是完全平衡的，因此您知道它需要 (m = sum(i=0..k)2^i) 个节点，因此需要 n-m 个节点留给最后一级。平衡二叉树的一些定义强制“所有节点左对齐”，在这种情况下，很明显只有一种可能性，没有这个约束，你有 2^floor(log(n) ) 选择 n-m，因为您必须选择 2^floor(log(n)) 可能的插槽中的哪个，您将分配给节点，强制总共要分配的 n-m 个节点。

对于高度故事，您考虑 2^floor(log(n)) 的组合总和选择 i 作为 i 来自1 到 2^floor(log(n))。您考虑在最后一级有 1 个节点的所有可能性，然后是 2 等等，直到您不使它成为完全平衡的二叉树，因此所有 2^floor(log(n))分配的插槽。