68ms C++ solution using binary search with brief explanation.


  • 30
    D

    The thought is simple. We just consider the lowest level of the tree.
    The left child and right child just divide the tree lower than the current node to 2 part.
    So what this code do is first check the right most child of the current node's left child.
    If this child is exist, we know that there may be more nodes on the right side of the tree. So we move the current node to it's right child. And repeat until we reach the lowest level.

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

  • 0
    Y

    I got very confused... what does "1<<height)-1" mean? and why does that work? I think it should be exponential. like Math.pow(2, height) - 1. Could you explain it? Thanks!


  • 0
    D

    The tree height start from 1, so if you only have a root node, the height will be 1. In this case I just shift the 1 bit left (height - 1) times to get 2^(height - 1).


  • 0
    Y

    got it! it is left shift by (height-1) times. it is bit operation. thanks!


  • 2

    Hi,

    Great code, excellent abstraction! I have the same idea and could only achieve 104 ms. Most of other methods posted will visit the branches that already visited. But binary search won't. And it's not easy to write code even if the idea is simple.


Log in to reply
 

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