在这个问题中 balanced 的定义是
balanced
其左子树中的节点数和右子树中的节点数几乎相等，这意味着它们的差异不大于1
如果给出一个 n 作为总节点数，有多少这样的树？
n
如果我们用 height 替换 the number of nodes 怎么办？鉴于 height ，有多少高度 balancer 的树木？
height
the number of nodes
那么差异只会由最后一个级别进行，因此您可以找到应该为该区域留下多少个节点，并且只考虑所有可能的组合 . 拥有 n 节点你知道高度应该是 floor(log(n)) 因此深度 k = floor(log(n)) - 1 的同一棵树是完全 balancer 的，因此你知道需要（ m = sum(i=0..k)2^i ）节点，因此 n-m 节点留给最后一级 . balancer 二叉树的一些定义强制"all the nodes to be left aligned"，在这种情况下显然只有一种可能性，没有这种约束你有 2^floor(log(n)) 选择 n-m 的组合，因为你必须选择你将分配哪些 2^floor(log(n)) 可能的插槽节点，强制分配总共 n-m 个节点 .
floor(log(n))
k = floor(log(n)) - 1
m = sum(i=0..k)2^i
n-m
2^floor(log(n))
对于高度故事，你考虑 2^floor(log(n)) 的组合之和选择 i ，因为 i 从1到 2^floor(log(n)) . 你考虑在最后一级有1个节点，然后是2等等的所有可能性，直到你没有使它成为一个完全 balancer 的二进制树，因此分配了所有 2^floor(log(n)) 个槽 .
i
1 回答
那么差异只会由最后一个级别进行，因此您可以找到应该为该区域留下多少个节点，并且只考虑所有可能的组合 . 拥有
n节点你知道高度应该是floor(log(n))因此深度k = floor(log(n)) - 1的同一棵树是完全 balancer 的，因此你知道需要（m = sum(i=0..k)2^i）节点，因此n-m节点留给最后一级 . balancer 二叉树的一些定义强制"all the nodes to be left aligned"，在这种情况下显然只有一种可能性，没有这种约束你有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等等的所有可能性，直到你没有使它成为一个完全 balancer 的二进制树，因此分配了所有2^floor(log(n))个槽 .