124. Binary Tree Maximum Path Sum
给你一个二元树，找出最大的一个路径和，路径可以不通过root节点。
Example：
https://assets.leetcode.com/uploads/2020/10/13/exx1.jpg
Input: root = [1,2,3]
Output: 6
Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.
https://assets.leetcode.com/uploads/2020/10/13/exx2.jpg
Input: root = [-10,9,20,null,null,15,7]
Output: 42
Constraints:
-1000 <= Node.val <= 1000
思路：
1.我们可以把任意node的所有路径切成四种情况：
(1) root本身就是最大路径 [1,-1,-1]
(2) root + 左Path 是最大路径 [1,1,-1]
(3) root + 右Path 是最大路径 [1,-1,1]
(4) root + 左右Path是最大路径 [1,1,1]
2.所以我们对树做DFS并判断上面的四种Case，不断的更新max的值，当node为空的时候返
回下限值（-1001）即可。
3.需要注意的是DFS的返回值必须是root、root+左路径、root+右路径其中一个，因为
Path不能有两个Edge。
Java Code：