I found this solution very helpful. 80 ms solution , consise and efficient. beats 90% submissions


  • 5
    R
    int countNodes(TreeNode* root) {
            if(!root) return 0;
            int num=1;
            TreeNode *curR(root->left), *curL(root->left);
            while(curR) // curR is the rightmost edge, which has a height equal to or less than the leftmost edge
            {
                curL = curL->left;
                curR = curR->right;
                num = num<<1;
            }
            return  num + ( (!curL)?countNodes(root->right):countNodes(root->left) );
        }

  • 0
    A

    how u r calculating last level node???


  • 0
    R

    @Aditi123456
    curR is the right edge of the left subtree;
    if (curL == NULL) it means that the left subtree is full and its size plus 1 (root node) is num, then calculate the right tree;
    if (curL != NULL) it means that left subtree is not full, but right subtree must be full; The num means the total nodes of right subtree plus 1(root node), so calculate the left subree;


Log in to reply
 

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