平衡二叉树

定义：

• 可以时一颗空树
• 他的左子树和右子树的高度之差的绝对值不超过 1
• 他的左子树和右子树都是一颗平衡二叉树

一、高度为 N 的平衡二叉树最少需要多少个节点？

答案是：f(n) = f(n-1) + f(n-2) + 1 (n >= 3)

我们首先这颗平衡二叉树为 T，他的最少节点数为 f，他的左子树为 TL，他的右子树为 TR。TL 和 TR 都是平衡二叉树，并且左右子树的最少节点为 f1 和 f2。那么我们此时可以得到 f = f1 + f2 + 1。我们现在只需要 f1 和 f2 最小即可。

由于 TL 和 TR 都是平衡二叉树，那么 TL 和 TR 的高度要么相同，要么相差为 1。那么 TL 和 TR 的高度相同时，明显节点数不是最少的。只有 TL 和 TR 的高度差 1，节点数才能最小。

那么当平衡二叉树的树高为 n，最少节点数为 f(n)，TL 和 TR 两个子树就应该为 f(n-1) 和 f(n-2)。最后再加上当前的节点。即可得出：f(n) = f(n-1) + f(n-2) + 1 (n >= 3)