222. Count Complete Tree Nodes

發表於 | 分類於

problem

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int countNodes(TreeNode* root) {
        if(!root) return 0;
        
        TreeNode *l = root, *r = root;
        int lh =0, rh= 0 ;
        while(l){
            l=l->left;
            lh++;
        }
        while(r){
            r=r->right;
            rh++;
        }
        if(lh == rh) return pow(2,lh)-1;
        return 1+countNodes(root->left)+countNodes(root->right);
        
    }
};

analysis

  • time complexity O(logn)
  • space complexity O(n)