# C++_iterative_Accepted_112ms_86.09%_With brief explanation

• I try to use iterative method rather than recursive for saving time.
• Try to use << rather than pow() function.

• Just look at this tree. If we use left node and right node to reach their left-end respectively, we can compare the heights and find out which part is losing right-end.

• For this tree, we first use node2 and node3 and find that the length of their left-end is the same, so we can deduce that we only need to search the right node. So we set root as root->right.

• Repeat above algorithm and then we find that the left is longer than right, so we only need to search the left part of the node.

• Until root == NULL.

• As for counting the nodes, if height of left node > right node, it means that the right node is a full tree, so we set res += 1 << right_count; else we will set res += 1 << left_count.

Code:

``````class Solution {
public:
int countNodes(TreeNode* root) {
if(root == NULL) return 0;
int res = 0;

while(root){
int lcount = 0, rcount = 0;
for(TreeNode* pleft = root->left; pleft; pleft = pleft->left){lcount++;}
for(TreeNode* pright = root->right; pright; pright = pright->left){rcount++;}
if(lcount > rcount){
root = root->left;
res += 1 << rcount;
}else{
root = root->right;
res += 1 << lcount;
}
}
return res;
}
};
``````

Time:

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