C# accepted, 188ms, Post-Order traversal, easy to understand


  • 1
    R
    public class Solution 
    {
            public int MaxPathSum(TreeNode root)
            {
                int max = Int32.MinValue;
                Travel(root, ref max);
                return max;
            }
    
            public int Travel(TreeNode root, ref int max)
            {
                // null node, sum is zero
                if (root == null)
                {
                    return 0;
                }
                
                // leaf node, sum is node value
                if (root.left == null && root.right == null)
                {
                    max = Math.Max(max, root.val);
                    return root.val;
                }
                
                // left
                int leftMax = Travel(root.left, ref max);
                
                // right
                int rightMax = Travel(root.right, ref max);
                
                // current max, is either root.val, or left path sum, or right path sum
                int currentMax = Math.Max(root.val, leftMax > rightMax ? leftMax + root.val : rightMax + root.val);
                
                // update global max
                max = Math.Max(max, currentMax);
                max = Math.Max(max, leftMax + root.val + rightMax);
    
                return currentMax;
            }
    }

Log in to reply
 

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