Binary-search: Consider the last row as an array O(log(n)^2) 36ms


  • 0
    X

    The code is a bit ugly. :(

    class Solution {
    public:
        int countNodes(TreeNode* root) {
            if (!root) return 0;
            int height = 0;
            TreeNode *x = root;
            while (x->left) {
                ++height;
                x = x->left;
            }
            int lo = 0, hi = (1 << height) - 1, level = 1;
            while (lo < hi) {
                int mid = lo + (hi - lo) / 2;
                x = root->left;
                for (int i = level; i < height; ++i, x = x->right);
                if (x) {
                    lo = mid + 1;
                    root = root->right;
                } else {
                    hi = mid;
                    root = root->left;
                }
                ++level;
            }
            return (1 << height) + (root ? 0 : -1) + hi;
            // return (1 << height) - 1 + (root ? 1 : 0) + hi;
        }
    };
    

Log in to reply
 

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