平衡二叉樹最少有幾個結(jié)點？

對于一棵平衡樹，如果以NhNh表示深度為h時含有的最少結(jié)點數(shù)。有如下的規(guī)律：

N0=0,N1=1,N2=2;Nh=Nh?1+Nh?2+1

這里研究的是最小結(jié)點數(shù)，最多結(jié)點數(shù)自然是滿二叉樹時的，不必像最少結(jié)點這樣需要遞推分析。

最少結(jié)點的情況還可以從平衡因子看：所有非葉結(jié)點的平衡因子均為1。可以推論的是，均為-1也是最少結(jié)點的情況。

通常會圍繞著最少結(jié)點，最大深度反復(fù)考察這個知識點。比如給定深度問最少需要多少個結(jié)點。或者給定結(jié)點數(shù)問最大能達到多少深度。

因此這個知識點可以形象化為深度是想達成的效果，越大越好，結(jié)點數(shù)是花費的成本，越小越好。