68 ms C++ solution using binary search


  • 0
    S
    //222 Count Complete Tree Nodes
    int countNodes(TreeNode* root) {
    	if (!root) return 0;
    	int ret = 0, height = 0;
    	auto cur = root;
    	while (cur) {
    		ret += (1 << height);
    		cur = cur->right;
    		++height;
    	}
    	while (height > 1) {
    		cur = root->right;
    		int h = height - 2;
    		while (h) {
    			cur = cur->left;
    			--h;
    		}
    		if (cur->left && !cur->right) {
    			ret +=  (1 << (height - 1)) + 1;
    			return ret;
    		}
    		else {
    			if (cur->left&&cur->right) {
    				ret += (1 << (height - 1));
    				root = root->right;
    			}
    			else root = root->left;
    			--height;
    		}
    	}
    	if (root->left&&root->right) ret += 2;
    	else if (root->left&&!root->right) ret += 1;
    	return ret;
    }

  • 0
    This post is deleted!

  • 0
    Y

    Could you explain your solution, please?


Log in to reply
 

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