class Solution {
public:
int countNodes(TreeNode* root) {
if(!root) return 0;
int hl=0, hr=0;
TreeNode *l=root, *r=root;
while(l) {hl++;l=l>left;}
while(r) {hr++;r=r>right;}
if(hl==hr) return pow(2,hl)1;
return 1+countNodes(root>left)+countNodes(root>right);
}
};
Easy short c++ recursive solution

Using a extra function,the height of left branch could be calculate only once.below is my c solution
int recursiveCountWithHeight(struct TreeNode* root,int height) { if(NULL==root) return 0; struct TreeNode *p=root; int r_h=0; while(NULL!=p){ ++r_h; p=p>right; } if(height==r_h){ return pow(2,height)1; }else{ return 1+recursiveCountWithHeight(root>left,height1) +recursiveCountWithHeight(root>right,height1); } } int countNodes(struct TreeNode* root) { if(NULL==root) return 0; struct TreeNode *p=root; int height=0; // left height only needs to be calculated once while(NULL!=p){ ++height; p=p>left; } return recursiveCountWithHeight(root,height); }

it is accepted.but on second thoughts I think u r right about it.when the right subtree is a complete tree and its height is one short than the left one,my solution will cause the calculation of the right part recursive needlessly,though it gives out the right answer,but the efficiency is reduced with no good reason.after modified the runtime of OJ is decrease from 74ms to 64 ms. thanks for your advice!

An improved method pair<int,int> CountCompleteNodes(TreeNode* root) { if(!root) { return make_pair(0,0); } int LeftLevel = 1; auto pLeft = root>left; while(pLeft) { LeftLevel++; pLeft = pLeft>left; } int RightLevel = 1; auto pRight = root>right; while(pRight) { RightLevel++; pRight = pRight>right; } if(LeftLevel == RightLevel) { return make_pair(pow(2, LeftLevel)1, LeftLevel); } auto RightNode = CountCompleteNodes(root>right); if(LeftLevel == RightNode.second) { return make_pair(pow(2, LeftLevel1)1+RightNode.first, LeftLevel); }else { auto LeftNode = CountCompleteNodes(root>left); return make_pair(1+LeftNode.first+RightNode.first, LeftLevel); } }

you either get two perfect binary tree or a perfect + a nonperfect. So a perfect + a nonperfect is already the worst case
as for how likely? (I could be wrong), there are possible (0 ~ 2^h) nodes in the bottom level. The only two cases that gives a perfect binary tree is 0, 2^h. So probability is (2^h + 1  2) / (2^h + 1)


@vanbasten23 no,in best case, left depth==right depth, so take constant time to calculate.
in the worst case, one of the left and right tree is a full tree, so T(n)=T(n/2)+....;

@redace85 I think this code is exactly the same but why does it TLE?
int countNodes(TreeNode* root) { if(root == NULL) return 0; TreeNode* l = root; int hl = 0; while(l){ l = l>left; hl++; } return countWithLeftHeight(root,hl); } int countWithLeftHeight(TreeNode* root, int hl){ if(root == NULL) return 0; TreeNode* r = root; int hr = 0; while(r){ r = r>right; hr++; } if(hl == hr){ return (1<<hl)  1; } return 1 + countWithLeftHeight(root>left,hl1) + countWithLeftHeight(root>right,hl1); }

nice solution~ i think height can be reused when countNodes(root>left) like:
class Solution(object): def left_height(self, root): height = 0 while root is not None: root = root.left height += 1 return height def right_height(self, root): height = 0 while root is not None: root = root.right height += 1 return height def count(self, root, left, right): if left == 1: left = self.left_height(root) if right == 1: right = self.right_height(root) if left == right: return 2**right1 else: return 1+self.count(root.left, left1, 1)+self.count(root.right, 1, right1) def countNodes(self, root): return self.count(root, 1, 1)