说明：

计算“<mark>计算AVL树h高度时候，最小的节点数</mark>”

使用公式：
a h = a h − 1 + a h − 2 + 1 a_h=a_{h-1}+a_{h-2}+1 ah​=ah−1​+ah−2​+1
a h : A V L 树 h 高 度 时 候 ， 最 小 的 节 点 数 a_h:AVL树h高度时候，最小的节点数 ah​:AVL树h高度时候，最小的节点数

代码

package cn.edut.tree;

public class Demo_countHofAVL {
	/** * 计算AVL树h高度时候，最小的节点数 * @param args */
	public static void main(String[] args) {
		int i = 50; 
		System.out.println(countHeight2(i));
		System.out.println(countHeight(i));
	}
	
	/** * O(2^N) 好像是。。。 * 不适合用递归的例子 * @param h * @return */
	public static long countHeight(int h ) {
		switch(h) {
		case 0 :  return 1 ;
		case 1 : return 2 ; 
		default : return countHeight(h-1)+ countHeight(h-2) +1 ;
		} 
	}
	
	
	/** * O(n) * @param h * @return */
	public static long countHeight2(int h ) {
		switch(h) {
		case 0 :  return 1 ;
		case 1 : return 2 ; 
		default :
			long a0 = 1 ; 
			long a1 = 2 ;
			long result = 0 ; 
			for(int i=1 ; i<h ; i++) {
				result = a0 + a1 +1  ;
				a0 = a1 ; 
				a1 = result ;
			}
			return result ;
		}
	}
}