222的終極解法，求時間複雜度

1. class Solution {
   
2. 
   
3.      K = 最後一排滿打滿算的全部元素個數D = 樹的層數
   
4.          
   
5.   // O(lgK * D)  ??????
   
6.    
   
7.   public int countNodes(TreeNode root) {
   
8.    
   
9.         if(root == null) return 0;
   
10. 
    
11.         int depth = countDepth(root);
    
12. 
    
13.         // 找到最後一層的所有位置(滿打滿算)
    
14.         int left = 0;
    
15.         int right = (int) Math.pow(2, depth - 1) - 1;
    
16. 
    
17.         while (left + 1 < right) {
    
18. 
    
19.             int mid = left + (right - left) / 2;
    
20. 
    
21.             if (  exist(mid, depth, root)  ) {   
    
22. 
    
23.               left = mid;
    
24. 
    
25.             } else{
    
26.                
    
27.               right = mid;
    
28.             }
    
29. 
    
30.         }
    
31.          
    
32.         if( exist(right, depth, root ) ) {
    
33.             
    
34.             return (int) Math.pow(2, depth - 1) + right;
    
35.             
    
36.         } else {
    
37.             
    
38.             return (int) Math.pow(2, depth - 1) + left;
    
39.         }
    
40.   }
    
41.       
    
42.   // Count the tree depth   
    
43.   public int countDepth(TreeNode root){  
    
44.   
    
45.         if(root == null) return 0;
    
46.    
    
47.         if(root.left == null) return 1;
    
48.          
    
49.         return countDepth(root.left) + 1;
    
50.   }
    
51.      
    
52.   // see if it is exist   
    
53.   public boolean exist(int Target, int D, TreeNode node){
    
54.   
    
55.      int L = 0;
    
56.       
    
57.      int R = (int) Math.pow(2, D - 1) - 1;
    
58.       
    
59.      // 用L和R是否重疊來判斷，是否到達最後一層
    
60.      while( L < R) {
    
61.       
    
62.               int mid2 = L +  (R - L)/2;
    
63.    
    
64.               if( Target <= mid2 ) {
    
65.                
    
66.                     R = mid2 ;
    
67.                     node = node.left;
    
68.               }
    
69.          
    
70.               if( Target > mid2 ) {
    
71. 
    
72.                     L = mid2 + 1;
    
73.                     node = node.right;
    
74.               }
    
75.      }
    
76.    
    
77.       
    
78.      /* 用層數來判斷是否到達最後一層
    
79.       int currentLevel = 1;
    
80.       
    
81.       while( currentLevel < D) {            
    
82. 
    
83.           int mid2 = L +  (R - L)/2;
    
84. 
    
85.           if( Target > mid2 ) {
    
86. 
    
87.             L = mid2;
    
88.             node = node.right;
    
89.           }
    
90. 
    
91.           if( Target <= mid2 ) {
    
92. 
    
93.               R = mid2;
    
94.               node = node.left;
    
95.           }
    
96. 
    
97.           currentLevel++;
    
98.        }
    
99.      */
    
100.       
     
101.     return node != null;
     
102.   }
     
103. }
     
104. 
     
105. 
     
106. 
     

复制代码

這個雙層 binary search 的解法，速度上pk掉所有其他解法。但我算不出他的時間複雜度。

求大神賜教！

我已陣亡。

countNodes 二分调用 exist O(log) 次，每次 exist 运行从根到底 O(log) 层，总计O((log n)^2)，介于 O(log n) 和 O(n) 中间。

usr_opta 发表于 2021-1-2 14:48
countNodes 二分调用 exist O(log) 次，每次 exist 运行从根到底 O(log) 层，总计O((log n)^2)，介于 O(log ...

可以再詳細一點嗎？  

第一次二分是Lg N  -->  N 是2^d     d是層數

第二次二分是d,  d是層

所以我覺得是  d*lg (2^d) = d^2???

techDiscussion 发表于 2021-1-2 15:03
可以再詳細一點嗎？  

第一次二分是Lg N  -->  N 是2^d     d是層數

一样的，我说的n是节点数量，你的d是层数，d=O(log n)
O((log n)^2) 等价于 O(d^2)