已知AVL树最浅叶子深度为k，求最少节点数的O(1)解法

你的思路完全正确：要满足最浅叶子深度为k且节点数最少，此时AVL树的高度必然等于k——如果树的高度大于k，要么会出现深度小于k的叶子，要么节点数会更多，不符合“最少节点”的要求。所以问题本质就是求高度为k的AVL树的最少节点数，且需用非递归的O(1)方法计算。

核心转化：关联斐波那契数列 #

你提到的递归公式 N(h) = N(h-1) + N(h-2) + 1（初始条件N(0)=0，N(1)=1），可以和标准斐波那契数列直接挂钩：
设标准斐波那契数列定义为 F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)，通过数学归纳法可证明：
N(h) = F(h+2) - 1

验证几个基础值：

• 当h=0（空树）：N(0)=0，F(2)-1=1-1=0，符合
• 当h=1（单节点树）：N(1)=1，F(3)-1=2-1=1，符合
• 当h=2（根+左右子节点）：N(2)=2，F(4)-1=3-1=2，符合

O(1)计算的关键：斐波那契通项公式 #

斐波那契数列有现成的通项公式（比内公式），可以在O(1)时间内计算任意项的值：
F(n) = (φⁿ - ψⁿ)/√5
其中：

• φ = (1 + √5)/2 ≈ 1.618（黄金分割比例）
• ψ = (1 - √5)/2 ≈ -0.618，且|ψ| < 1

将这个公式代入N(h)的表达式，得到：
N(k) = ((φ^(k+2) - ψ^(k+2))/√5) - 1

由于|ψ| < 1，当k≥0时，ψ^(k+2)的绝对值会随k增大快速趋近于0，且始终小于0.5，因此可以通过取整简化计算（避免浮点数精度问题）：
N(k) = floor(φ^(k+2)/√5) - 1

这个公式无需递归或迭代，直接通过数学运算就能得到结果，时间复杂度为O(1)。

内容的提问来源于stack exchange，提问作者PiTheta1729