Leetcode/微软百度 -- 124. Binary Tree Maximum Path Sum(DFS)

124. Binary Tree Maximum Path Sum(DFS)
Hard
https://leetcode.com/problems/binary-tree-maximum-path-sum/#/description

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.

思路： At every node, the max path formed by node's val + left child path (>0) + right child path(>0)
          Since we can only have 1 parent node in path, when we do recursive call,
          - in helper: for each child node, we add the node's val with either its left or right path or nothing.
          - keep track the max vs path sum pass through current node as the parent node

Complexity：  Time O(n) Space O(h)

public class Solution {
    int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        helper(root);
        return max;
    }
    //Path pass parent node only once
    //at every node, either add its left or right path or nth for n
    public int helper(TreeNode root){
        if(root == null) return 0;
        int sum1 = Math.max(0, helper(root.left));
        int sum2 = Math.max(0, helper(root.right));
        max = Math.max(max, sum1 + sum2 + root.val);
        return root.val + Math.max(sum1, sum2);
    }
}