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

  • 5
    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

    how u r calculating last level node???

  • 0

    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.