C++ binary search solution using coded path


  • 0
    B
    class Solution {
    public:
    int getHeight(TreeNode* u, int x, int ht) {
    	int height = 0;
    	int test = 1 << (ht - 1);
    	while (u) {
    		if ((test&x) == 0)	u = u->left;
    		else u = u->right;
    		test >>= 1;
    		height++;
    	}
    	return height - 1;
    }
    
    int countNodes(TreeNode* root) {
    	TreeNode* u = root;
    	if(!u) return 0;
    	int height = 0;
    	while (u) {
    		u = u->left;
    		height++;
    	}
    	height--;
    
    	int left = 0, right = (1 << height) - 1;
    
    	while (left <= right) {
    		int mid = (left + right) >> 1;
    		int ht;
    		if (mid == 0)
    			ht = height;
    		else
    			ht = getHeight(root, mid, height);
    		if (height == ht) {
    			left = mid + 1;
    		}
    		else {
    			right = mid - 1;
    		}
    	}
    
    	return right + (1 << height);
    
    }
    

    };


Log in to reply
 

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