c++ beats 70% count nodes by mainly comparing levels of subtrees in a loop


  • 0
    3
    if(root==NULL)
                return 0;
            int level;
            level=countlevel(root);
            TreeNode *leftchild,*rightchild;
            int ll,rl,nodes,lastnodes,flag;
            flag=0;
            nodes=1;lastnodes=1; // lastnodes: number of nodes on the last completed level 
            for(int i=1;i<level-1;i++)
            {
                nodes+=2*lastnodes;
                lastnodes*=2;
            }
            leftchild=root->left;
            rightchild=root->right;
            while(leftchild||rightchild)
            {
                ll=countlevel(leftchild);
                rl=countlevel(rightchild);
                if(ll==rl)
                {
                    nodes+=lastnodes;
                    lastnodes/=2;
                    leftchild=rightchild->left;
                    rightchild=rightchild->right;
                    flag=1;
                }
                if(ll!=rl)
                {
                    if(!(leftchild&&rightchild))
                        nodes+=lastnodes; 
                    lastnodes/=2;
                    rightchild=leftchild->right;
                    leftchild=leftchild->left;
                    flag=0;
                }
            }
            if(flag)
                nodes+=1;
            return nodes;
        }
        int countlevel(TreeNode* root)
        {
            if(root==NULL)
                return 0;
            int level=1;
            TreeNode *leftmost=root->left;
            while(leftmost)
            {
                ++level;
                leftmost=leftmost->left;
            }
            return level;
        }

Log in to reply
 

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