高度为8的平衡二叉树的结点数至少有

Question

高度为8的平衡二叉树的结点数至少有（）个。

有第二种解题方法，后面那个斐波那契那里不明白，

Answer 1

设F(n)表示第n个斐波那契数，即F(1) = 1, F(2) = 1, F(n) = F(n-1) + F(n-2) (n > 2)。则有：

S(1) = 1
S(2) = 2
S(k) = S(k-1) + S(k-2) + 1 (k > 2)

将S(k)看做F(k+1) - 1，则有：

F(2) - 1 = S(1)
F(3) - 1 = S(2)
F(k+1) - 1 = S(k) = S(k-1) + S(k-2) + 1 = F(k) + F(k-1) + 1 (k > 2)

因此，对于高度为8的平衡二叉树，其节点数至少为F(9) - 1 = 34个。