7-line and easy-understand java solution

  • 1

    a path, must be composed of the top node itself, and left branch(can be null) and right branch (can be null)
    so we traverse the tree, and treat each node we traversed as top node, calculate the max value. How I do this: I recursively call a search function, which calculate the max sum of left branch and right brach. Considering negative value, so if the max sum of a branch is negative, obviously we will drop it (I just set its value to zero)
    And then we calculate the max sum of current node(as top node) as :
    maxSum = current_node_val +max(left_branch,0)+max(right_branch,0)

    and we return the maxsum of this branch as called by upper layer as:
    maxSum_branch = current_node_val+max( max(left_branch,0), max(right_branch,0) )

    Also I use a global variable to record the maxSum

    class Solution {
        private int max = Integer.MIN_VALUE;
        public int maxPathSum(TreeNode root) {
            return max;
        private int search(TreeNode node) {
            int l, r;
            l = node.left == null ? 0 : Math.max(search(node.left), 0);
            r = node.right == null ? 0 : Math.max(search(node.right), 0);
            max = Math.max(max, l + r + node.val);
            return node.val + Math.max(l, r);

Log in to reply

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