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：