Beating 99.84% submissions in C++, quite intuitive and well-commented


  • 4

    What are we doing here is to collect the additional last-level leaves, always stick this in mind when reading the code below.


    class Solution {
    public:
        int countNodes(TreeNode* root) 
        {
            if(!root) return 0;
            int height = 0, sum = 0, i = 0;
            TreeNode *t = root, *t0 = NULL;
            while(t) t = t->left, height++; //get the height of the tree;
            t = root;
            int level = height - 2; //levels under the child of root;
            while(level > -1) //collect the bottom-level nodes by halving them apart;
            {
                t0 = t->left;
                for(i = 0; i < level; ++i) t0 = t0->right; 
                if(t0) { sum += 1<<level; t = t->right; } //rightmost node is not null;
                else t = t->left;
                level--; //move to the next level;
            }
            if(t) sum++; //if it's a complete tree, collect the last right node;
            return sum+((1<<(height-1))-1);
        }  
    };

  • 0

    Another binary-search solution is also enclosed here.

    One reminder here: the time cost is accelerated from 248ms to 124ms just by replacing the pow(2, r) to (1<<r).


    class Solution {
    private:
        int lheight(TreeNode* root)
        {
            int depth = 0;
            while(root) root = root->left, depth++;
            return depth;
        }
    public:
        int countNodes(TreeNode* root) 
        {
            if(!root) return 0;
            int l = lheight(root->left), r = lheight(root->right);
            if(l > r) return countNodes(root->left)+(1<<r);
            else return countNodes(root->right)+(1<<l);
        }
    };

  • 0

    Then using in-line loop to replace function invoking, reduce the time to 112ms.

    class Solution {
    public:
        int countNodes(TreeNode* root) 
        {
            if(!root) return 0;
            int lCount = 0, rCount = 0;
            for(TreeNode* l = root->left; l; l = l->left) lCount++;
            for(TreeNode* r = root->right; r; r = r->left) rCount++;
            if(lCount > rCount) return countNodes(root->left)+(1<<rCount);
            else return countNodes(root->right)+(1<<lCount);
        }
    };

  • 0

    Using iterative solution to update the previous recursive one reduce the time to 100ms now.

    class Solution {
    public:
        int countNodes(TreeNode* root) 
        {
            if(!root) return 0;
            int sum = 0, lCount = 0, rCount = 0;
            while(root)
            {
                lCount = 0, rCount = 0;
                for(TreeNode* l = root->left; l; l = l->left) lCount++;
                for(TreeNode* r = root->right; r; r = r->left) rCount++;
                if(lCount > rCount) root = root->left, sum += (1<<rCount);
                else root = root->right, sum += (1<<lCount);
            }
            return sum;
        }
    };

  • 0

    Conclusion:

    Compared to the best submission 72ms, all the solutions above have done lots of re-checking when measuring the height, while the best only check it once and then all the following checking will only take one traversal while the other solutions are doing two - left and right.


  • 0
    H

    @LHearen Smart!


  • 0
    Q

    @LHearen
    Your algorithm of first solution is brilliant and unusual. Usually a algorithm of Tree consider the the left and the right child, but you are considering the left child's left and right path.
    Somehow this requires a hard-memorization to utilize your algorithm in interview.

    One thing that bothers me is your comment on this line, which I think is misleading:
    if(t) sum++; //if it's a complete tree, collect the last right node;
    collect the last right node is an accurate description, but I don't see why you want to say it is a complete tree.
    Apparently when you quit the loop while(level > -1) , t is at the bottom level, either a NULL pointer or left child of its parent and no right sibling.
    I think the comment should be //if it's the single left child of it's parent, we add it to the sum (pow(2, 0) )

    Regards,

    Quesder


  • 0

    @quesder Your observation is sharp indeed, however what I exactly meant here is the t instead of t0 (the child of t) at the last loop, if the t0 is again valid then t will move to its right child (the last only leaf), which is why I will check it and if it's a leaf not NULL then I added a perfect complete tree comment.


Log in to reply
 

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