问个复杂度。CC150上的判断一个树是否平衡

1. package bianryTree;
   
2. 
   
3. public class treeBalanced {
   
4. public static int getHeight(Node root){
   
5.         if(root==null) return 0;
   
6.        
   
7.         return (Math.max(getHeight(root.getLeft()),getHeight(root.getRight())+1));
   
8. }
   
9.        
   
10. 
    
11. public static boolean isBalanced(Node root){
    
12.         if(root==null) return true;
    
13.        
    
14.         int diff=getHeight(root.getLeft())-getHeight(root.getRight());
    
15.         if(Math.abs(diff)>1){
    
16.                 return false;
    
17.                
    
18.         }else{
    
19.                
    
20.                 return isBalanced(root.getLeft())&&isBalanced(root.getRight());
    
21.                
    
22.         }
    
23.        
    
24.        
    
25. }
    
26. 
    
27.        
    
28. }
    

复制代码

getHeight递归调用所有的节点为O（N），isBalanced也是O（N），嵌套进去应该是O（N×N）吧，为什么答案写的是O（N×log（N））？

getHeight 平均复杂度是logN，不是N。

kmeans 发表于 2014-10-14 13:41
getHeight 平均复杂度是logN，不是N。

點解？詳細點羅~

getHeight复杂度
第一层
root 是N
第二层
root.left 是 1/2 N
root.right 是1/2 N
...
每层getHeight之和近似是N， 总共longN层， 所有节点的getHeight 之和是NlogN