LeetCode 124. Binary Tree Maximum Path Sum
原题链接在这里：https://leetcode.com/problems/binary-tree-maximum-path-sum/
题目：
Given a non-empty 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.
Example 1:
Input: [1,2,3]
1
/
2 3
Output: 6
Example 2:
Input: [-10,9,20,null,null,15,7] -10 / 9 20 / 15 7 Output: 42
题解：
dfs函数是求当前root往下的最大路径. DFS states needs current tree node.
先算左边路径，返回值直接和0比较, 若不是正数就返回0, 然后同样方法算右边路径.
更新res[0], 看看当前root的val同时加上左边和右边有没有比现有的res[0]包含值大.
dfs 返回当前最深路径看当前root的val加上左边或者右边, 哪个大, dfs函数返回大的那个.
Time Complexity: O(n).
Space: O(logn).
AC Java:
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */ 10 public class Solution { 11 public int maxPathSum(TreeNode root) { 12 if(root == null){ 13 return 0; 14 } 15 int [] res = {Integer.MIN_VALUE}; 16 dfs(root, res); 17 return res[0]; 18 } 19 20 private int dfs(TreeNode root, int [] res){ 21 if(root == null){ 22 return 0; 23 } 24 //自底向上的death-first 25 int leftMax = Math.max(0, dfs(root.left, res)); 26 int rightMax = Math.max(0, dfs(root.right, res)); 27 res[0] = Math.max(res[0], leftMax + rightMax + root.val); 28 29 return Math.max(leftMax, rightMax) + root.val; 30 } 31 }