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.

    0_1475788617941_D514B664-DB6A-4702-BBBD-A03D18B44652.png

    • 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:
    0_1475789022118_2F2A4342-8C57-4297-AC22-BC0FC147396A.png


Log in to reply
 

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