Iterative approach using queue & O(n) time complexity


#1

Logic: find max at each level and check if it is max so far

int Solution::solve(TreeNode* A) {
    queue<TreeNode*> q;
    if(A==NULL)  return -1;
    
    q.push(A);          
    q.push(NULL);       // to change level
    int mx=A->val;
    int m=0;            // sum of each level
    while(q.size()>1)
    {
        TreeNode* temp=q.front();
        q.pop();
        if(temp==NULL)
        {
            q.push(NULL);
            mx=max(mx,m);// updating value
            m=0;        // sum of next level 0
        }
        else
        {
            m+=temp->val;
            if(temp->left)  q.push(temp->left);
            if(temp->right) q.push(temp->right);
        }
    }
    mx=max(mx,m);       // checking for last level 
    return mx;
}