Solution beats 60 % with O(log(n) * log(n)) runtime using binary search


  • 0
    H

    Represent path as integer. Perform binary search on path. Looking up a leave node takes O(log n). I have to do O(log n) look-ups till I found last leave at lowest level.

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        // return max path/height
        int height(TreeNode *node) {
            int h = 0;
            
            while (node) {
                node = node->left;
                h++;
            }
            return h;
        }
        
        // traverse using path encoded as int
        bool traverse(TreeNode *node, long long path, int height) {
            int h = 0;
            
            for (int i = height - 2; i >= 0; i--) {
                if (path & (1 << i))
                    node = node->right;
                else
                    node = node->left;
                if (!node)
                    return false;
            }
            return true;
        }
    
        int countNodes(TreeNode* root) {
            long long begin = 0;
            long long end = 0;
            int height;
            
            // measure height for search space
            height = this->height(root);
            if (height == 0)
                return 0;
            for (int i = 0; i < height - 1; i++)
                end |= (0x1 << i);
    
            while (begin < end) {
                // search for lower bound
                long long m = begin + (end - begin + 1) / 2;
                if (traverse(root, m, height))
                    begin = m;      // include m
                else
                    end = m - 1;    // don't include m
            }
    
            // count complete part of tree
            int count = 0;
            int levelCount = 1;
            for (int i = 1; i <= height - 1; i++) {
                count += levelCount;
                levelCount *= 2;
            }
            
            // count incomplete part of tree
            count += begin + 1;
            
            return count;
        }
    };

Log in to reply
 

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