极客时间数据结构与算法之美笔记27

一个满二叉树的节点个数和高度有对应关系：高度h的满二叉树结点为2^h-1。
递归代码算法的时间复杂度，可以通过画递归树来推导出。

怎么推导？

斐波那契数列算法递归树

从上往下算，第一层的总时间消耗是 1，第二层的总时间消耗是 2，第三层的总时间消耗就是 2^2。依次类推，第 k 层的时间消耗就是 2^(k−1)，那整个算法的总的时间消耗就是每一层时间消耗之和。
也就是