80 ms C++ non-recursive solution


  • 3
    B
    class Solution {
        public: 
        int countNodes(TreeNode* root) { 
            int res = 0;
            int lh = 0, rh = 0;
            while(root){
                if(!lh){
                    for(TreeNode * p = root->left; p; p = p->left)
                        ++lh;
                }
                if(!rh){
                    for(TreeNode * p = root->right; p; p = p->left)
                        ++rh;
                }
                if(lh == rh){
                    res += 1<<lh;
                    root = root->right;
                    --lh;
                    rh = 0;
                }else{
                    res += 1<<rh;
                    root = root->left;
                    --lh;
                    rh = 0;
                }
            }
            return res;
        }
    };
    

    Reference: https://leetcode.com/discuss/54900/my-ac-c-solution


  • 0
    M

    @biwuxia
    I have another non-recursive solution using binary search.
    The key idea is to check if the k-th node exists by moving the 'node' pointer from 'root' to the right direction.

    class Solution {
    public:
        int countNodes(TreeNode* root) {
            if (root == NULL) return 0;
            int height = 0;
            TreeNode* n = root;
            while (n != NULL) {
                ++height;
                n = n->left;
            }
            
            int hi = (1<<(height-1)), low = 0;
            
            while (low < hi) {
                int mid = low + (hi - low) / 2;
                
                // Find the mid-th element of the bottom level.
                n = root;
                for (int h = height - 1; n != NULL && h > 0; --h) {
                    if (mid & (1 << (h-1))) {
                        n = n->right;
                    } else {
                        n = n->left;
                    }
                }
                
                if (n == NULL) {
                    hi = mid;
                } else {
                    low = mid + 1;
                }
            }
            return (1<<(height-1)) + hi - 1;
        }
    }; 
    

Log in to reply
 

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