C# Simple Recursive Accepted solution-No extra space (not counting recursion)


  • 0
    J

    This idea is somewhat similar to a DP solution. For any node, it's value needs to be added if a path is going through the node. For said node, the optimal sum would be it's value, plus the optimal solution of it's left node and optimal solution of it's right node. But say the path also involves the parent of this node, then we can't count both the left and right child of this node because a path cannot have branches. Hence we choose the max of root.val + left and root.val + right. We should also consider the root val itself in case the left and right child values are negative.

    We maintain a global variable result, because the root doesn't necessarily need to be involved in the path. For example, the optimal sum may be present in the right subtree of a given node, but we still need to calculate the max path for this node.

    Please suggest any improvements or modifications.

    public class Solution {
        
        int result = int.MinValue;
        
        public int MaxPathSum(TreeNode root) 
        {
            if (root == null) return 0;
            Helper(root);
            return result;
        }
        
        public int Helper(TreeNode root)
        {
            if (root == null) return 0;
            if (root.left == null && root.right == null)
            {
                result = Math.Max(result, root.val);
                return root.val;
            }
            int thisoptimalsum;
            var leftoptimal = Helper(root.left);
            var rightoptimal = Helper(root.right);
            if (leftoptimal <= 0 && rightoptimal <= 0)
            {
                result = Math.Max(root.val, result);
                return root.val;
            }
            var possible1 = root.val;
            var possible2 = root.val + leftoptimal;
            var possible3 = root.val + rightoptimal;
            var possible4 = root.val + leftoptimal + rightoptimal;
            
            // for thisoptimalsum, we only compare the first three values because possible4, which takes root, left and right cannot be sent to root's parent. The path cannot have a branch. But we still compare it to the actual result because the root doesn't need to a be part of the path. 
            thisoptimalsum = Math.Max(possible1, Math.Max(possible2, possible3));
            result = Math.Max(result, Math.Max(possible4, thisoptimalsum));
            return thisoptimalsum;
        }
    }
    

Log in to reply
 

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