Binary search solution


  • 0
       bool get(TreeNode* t, int num) {
            if (num == 0) return true;
            int i = 1 << 30;
            for (; i; i >>= 1) {
                if (num & i) break;
            }
            i >>= 1;
            while (i && t) {
                t = (num & i) ? t->right : t->left;
                i >>= 1;
            }
            return t;
        }
        int countNodes(TreeNode* root) {
            if (!root) return 0;
            int lo = 0, hi = 1 << 30;
            while (lo + 1 < hi) {
                int mid = lo + (hi - lo) / 2;
                if (get(root, mid)) {
                    lo = mid;
                } else {
                    hi = mid;
                }
            }
            return lo;
        }
    

Log in to reply
 

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