124. Binary Tree Maximum Path Sum

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 must contain at least one node and does not need to go through the root.

For example:
Given the below binary tree,
       1
      / \
     2   3
Return 6.

Solution：分治(postorder) + DP

思路： 树的53. Maximum Subarray版本
Time Complexity: O(N) Space Complexity: O(N)

Solution Code：

class Solution {
    
    private int max_value;
    
    public int maxPathSum(TreeNode root) {
        max_value = Integer.MIN_VALUE;
        dfsMax(root);
        return max_value;
    }
    
    private int dfsMax(TreeNode node) {
        if(node == null) return 0;
        
        int left_max = Math.max(0, dfsMax(node.left));
        int right_max = Math.max(0, dfsMax(node.right));
        
        int cur_max =  left_max + right_max + node.val;
        if(cur_max > max_value) max_value = cur_max;
        
        return Math.max(left_max, right_max) + node.val;
    }
}