C++ 73ms.. beats 99.43% Based on binary search.


  • 2

    Find height of the tree and find the m = height of root->left (Right height of left subtree of Root)
    if m < height, it means right subtree of root is a perfect tree of height height-2. Add the no.of elements in this tree + 1(for root) into count, and focus on the left half.
    if m >= height, then left subtree is perfect with a height of height-1. Add no.of elements in this +1 to count and focus on right half.
    Decrement height after every iteration as we step down.

    int countNodes(TreeNode* root) {
        if(!root)
            return 0;
        int count = 0, height=0,m;
        TreeNode* temp = root;
        while(temp){
            ++height;
            temp=temp->left;
        }
        while(root){
            m = 1;
            temp=root->left;
            while(temp){
                ++m;
                temp=temp->right;
            }
            if(m<height){
                count = count + (1<<(height-2));
                root = root->left;
            }
            else{
                count = count + (1<<(height-1));
                root = root->right;
            }
            --height;
        }
        return count;
    }
    

    Outer loop runs till root becomes null. --> O(log n)
    Inside we find height m which takes --> O(log n)
    Overal Complexity = O(log n * log n)

    0_1477993828030_ss.jpg


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.