Share my C++ solution with explanation,beats 90% of submissions,easy to understand


  • 2
    V
    class Solution {
    public:
        int countNodes(TreeNode* root) {
            if (root == NULL)
                return 0;
            
            int height = 0;
            int cnt = 0;
            TreeNode *left = root->left;
            TreeNode *right = root->left;
    
            while(right != NULL)
            {
                height++;
                left = left->left;
                right = right->right;
            }
            
            cnt = (1 << height) - 1;
            /* <left == NULL && right == NULL> denotes the  left subtree of root must be a perfect binary tree. The right subtree? May be,may be not.
             * <left != NULL && right == NULL> denotes the right subtree of root must be a perfect binary tree. Similarly,it's not clear whether the left is
             * a perfect binary tree.
             * cnt denotes the number of nodes in the perfect binary tree, 1 denotes the root
             */
            if (left == NULL)
                return 1 + cnt + countNodes(root->right);
                    
            return 1 + cnt + countNodes(root->left);
        }
    };

Log in to reply
 

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