A different approach first choosing left or right sub-tree then get its count.


  • 0
    G
    class Solution {
    public:
        int myheight;
        void getheight(TreeNode* root,int &height)
        {
            if(root==NULL) return ;
            height++;
            getheight(root->left,height);
        }
        int countNodes(TreeNode* root) {
            if(root==NULL) return 0;
            myheight  = -1;
            getheight(root ,myheight);
            return getcount(root ,0, 0,0);
        }
        int getcount(TreeNode* root,int height,int width,int sum)
        {
            sum+=pow(2,height-1);
            if(root->left==NULL && root->right==NULL) return sum + width + 1;
            int var=height;
            getheight(root->right,var);
            if(var!=myheight)  getcount(root->left,height+1,width*2,sum);
            else getcount(root->right,height+1,width*2+1,sum);
            
        }
    };

Log in to reply
 

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