My solution is not very fast, but it's typical binary search!


  • 0
    P
    bool leafExist(TreeNode *root, int test, int n) {
        TreeNode *node = root;
        for (int i =n-2;i >= 0;i--)
            if ((1 << i) & test)
                node = node->right;
            else
                node = node->left;
        return node != nullptr;
    }
    
    int countNodes(TreeNode* root) {
        if (!root) return 0;
        int n = 0;
        TreeNode *node = root;
        while (node) {
            node = node->left;
            ++n;
        }
        if (n == 1) return 1;
        int start = 0, end = (1<<(n-1)) - 1, mid;
        int minus = 0;
        if (!leafExist(root,end,n)) {
            while (start != end - 1) {
                mid = (start+end)/2;
                if (leafExist(root,mid,n)) {
                    start = mid;
                } else {
                    end = mid;
                }
            }
            minus = (1<<(n-1)) - end;
        }
        return (1<<n) - 1 - minus;
    }

Log in to reply
 

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