有多少种不同的二叉树可以形成高度为h？

Question

可以形成多少种类型的不同的二叉树，其高度为h？如果我们只知道二叉树的高度，并且我们将根 - 左和右 - 右视为同一棵树结构，这意味着如果二叉树的高度等于1，则可以形成2种不同的树结构： root - leftchild/rightchild; root - leftchild - rightchild

Answer 1

让我们有S [h]方法来构建高度为h的树（（h） - 树）。
我们可以从根节点和从：
- 左（h-1）树和高度为0..h-2的任何右树组成树（h-tree）
-两个（h-1）树
- 右（H-1） - 树与高度0..h-2

所以递推公式任何左树

S[h] = S[h-1] * Sum{k=0..h-2} (S[k]) + 
     S[h-1] * S[h-1] + 
     S[h-1] * Sum{k=0..h-2} (S[k]) = 
     S[h-1] * (S[h-1] + 2 * Sum{k=0..h-2} (S[k])) 

现在有了S[0] = 1, S[1] = 1，我们可以找到递归所有值。

实施例：S[3] = S[2] * (S[2] + 2*(S[0] + S[1])) = 3 * (3 + 2 * (1 + 1)) = 21

注意，相同的值将被一次又一次地计算，所以它是值得使用动态规划：
- 或自顶向下memoization - 当我们写一次计算值S [K ]到表中并使用它，这是递归非常简单的修改
- 或自下而上的方法 - 在这里我们可以使用累加和的附加表。

检查：S[5] = 457653