C++_iterative_Accepted_112ms_86.09%_With brief explanation

  • 0
    • 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.


    class Solution {
    int countNodes(TreeNode* root) {
        if(root == NULL) return 0;
        int res = 0;
            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;
                root = root->right;
                res += 1 << lcount;
        return res;


Log in to reply

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