求110题的Recursion时间复杂度

代码如下，怎么分析这题的时间复杂度呢？  感觉每一层recursion都要调用子函数，然后子函数也是recursion的。细思极恐。

继续跪求一粒米～

1. class Solution {
   
2. 
   
3.      public boolean isBalanced(TreeNode root) {
   
4.          
   
5.          if(root == null) return true;
   
6.       
   
7.          return Math.abs(height(root.left) - height(root.right)) < 2 &&
   
8.                 isBalanced(root.left) &&
   
9.                 isBalanced(root.right);
   
10.      }
    
11.    
    
12.    
    
13.      public int height(TreeNode root) {
    
14. 
    
15.         if(root == null) return -1;
    
16. 
    
17.         return 1 + Math.max(height(root.left), height(root.right));
    
18.      }
    
19. }
    
20.    
    
21. 
    
22. 
    

复制代码

这个题的时间复杂度应该是“大约是O（nlogn）”； 因为每层遍历最多遍历n个，总共是logN层，所以时间复杂度的upper bound 是 O（nlogn) 但实际时间复杂度会小于这个值，所以我们只能说一个范围 介于O(n)~O(nlogn)之间。。。

conghao2016 发表于 2020-7-21 17:17
这个题的时间复杂度应该是“大约是O（nlogn）”； 因为每层遍历最多遍历n个，总共是logN层，所以时间复杂度 ...

感谢同学，你用java刷题吗？ 我在找zoom自习搭档