Very short and easy Java solution


  • 2
    Y

    Bottom-up approach. Build up max path from leaf to root. At each node cur, we check left + cur (left path + current root), right + cur (right path + current root), and left + cur + right (left path + current root + right path). Then we return max(left + cur, right + cur), because ancestors can only use one of the left or right paths.

    Later on I found checking left + cur, right + cur, left + cur + right unnecessary, because we don't actually want to return negative values to ancestors (it's like another Leetcode question: 53. Maximum Subarray). Then it's guaranteed that left >= 0 && right >= 0, and the max path sum at current root is simply: left + cur + right.

    Corner case: max path sum is a negative value (root is negative). Need to set result = root.val initially.

    Initial version (4ms):

    public class Solution {
        private int result;
        
        public int maxPathSum(TreeNode root) {
            result = root.val;
            getMaxPathSum(root);
            return result;
        }
        
        private int getMaxPathSum(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int left = getMaxPathSum(root.left);
            int right = getMaxPathSum(root.right);
            // check the path sum at current node (actually unnecessary, see concise version below)
            int sum = Math.max(left+right, Math.max(left, right)) + root.val;
            result = Math.max(result, sum);
            return Math.max(0, Math.max(left, right) + root.val);
        }
    }
    

    A more concise and faster version (2ms):

    public class Solution {
        private int result;
        
        public int maxPathSum(TreeNode root) {
            result = root.val;
            getMaxPathSum(root);
            return result;
        }
        
        private int getMaxPathSum(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int left = getMaxPathSum(root.left);
            int right = getMaxPathSum(root.right);
            // since we always return non-negative values, simply use (left + right + root.val) to get the max path sum
            result = Math.max(result, left + right + root.val);
            return Math.max(0, Math.max(left, right) + root.val);
        }
    }
    

Log in to reply
 

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