Binary Tree Maximum Path Sum

lc 124

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path does not need to go through the root.

public class Solution {
    public int maxPathSum(TreeNode root) {
        // variable globalMax, every node return 只是传过自己的最大值
        int[] res = new int[1];
        res[0] = Integer.MIN_VALUE;
        helper(root, res);
        return res[0];
    }

    public int helper( TreeNode root, int[] res){
        if ( root == null ) return 0;
        int left = helper (root.left, res);
        int right = helper(root.right, res);
        int arc = left + right + root.val;
        int single = Math.max(Math.max(left, right) + root.val, root.val);
        res[0] = Math.max(res[0], Math.max(arc, single));
        return single;
    }
}

    int maxValue;

    public int maxPathSum(TreeNode root) {
        maxValue = Integer.MIN_VALUE;
        maxPathDown(root);
        return maxValue;
    }

    private int maxPathDown(TreeNode node) {
        if (node == null) return 0;
        int left = Math.max(0, maxPathDown(node.left));
        int right = Math.max(0, maxPathDown(node.right));
        maxValue = Math.max(maxValue, left + right + node.val);
        return Math.max(left, right) + node.val;
    }