Question

平衡二叉树高为6,非叶结点的平衡因子都为 1,则节点总数是多少?为啥是20?求详解

Answer 1

显然这棵平衡二叉树为高度为6的最少结点数量

设 N 是深度为 h 的平衡二叉树的最少结点数,对于 h >= 1,有 N = F(h + 2) - 1 成立,其中的F(n)为Fibonacci 数列：1,1,2,3,5,8,13,21,34,55,...

于是对于h = 6,得到F(6 + 2) = 21,所以结点数目为21 - 1 = 20

那个公式的推导过程可以去参看比较全的数据结构教材