目標：
這題主要目的在於進階探索Tree較複雜的問題。

原題：

Question:
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 with 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

分析/解題：
題目給定一個二元樹，試求其上最大的路徑和的值。
所謂路徑，就是在二元樹上任意挑兩個節點，
從一個節點走到另一個節點，包含它們自己，所經過的所有節點值的和。
最小的條件是兩個節點相同，這時候的路徑長等同於這個節點的值。

嫌前面太簡單了嗎？別急，Hard等級的題目這不就來了嗎XD
在講解以前，建議讀者先思考一下有沒有任何頭緒並寫下來，
再接著往下面看分析，相信會有比較好的收穫。

3~

2~

1~

開始囉！

如果我們多拿幾組節點來進行觀察，會發現從一個節點要走到另一個節點，
要先經過它們最低的共同祖先節點
(這邊指從雙方往上走第一個碰頭的位置)，再走下來才行。
以Example 1來說，2和3的最低共同祖先是1，
以Example 2來說，15和7的最低共同祖先是20。

那麼，我們怎麼決定兩個節點的路徑長呢？
假設我們知道AB兩個節點的話，它們一定會有一個最低的共同祖先節點，
當中可能是A或B自身，也可能是其他節點
(如前面的範例就都是其他節點，
而如果取的是-10跟15的話那最低的共同祖先節點就是-10)，
所以每個節點都可以有做為節點的最低共同祖先節點的可能。

我們姑且將最低共同祖先節點叫做中繼點好了，比較方便XD
接著，將不含中繼點的左邊的最大路徑和叫做l，
右邊的最大路徑和叫做r，對於某個中繼點(node n)而言：

通過中繼點n的最大路徑和 = max(n.val, n.val + l, n.val + r, n.val + l + r)
(因為l或r都有可能是負的，所以要把這四種都考慮在內)

接著我們要考慮的是，如果中繼點是別的點而不是現在這個點，
我們只是經過它但想知道包含這個點往下走最大路徑和是多少的話，
那我們只能去考慮n.val / n.val+l / n.val+r這三種狀況。
(因為n.val+l+r代表這個點是做為中繼點才會有分支)

所以我們可以嘗試用遞迴的方式解題，從root開始往下走到每個節點，
計算該節點往下走的最大路徑和，
並且每經過一個節點就考慮看看這個節點是中繼點的狀況，
一旦發現最大值比現有記錄的大，就更新成新的最大值。
由於用來遞迴的函式是一路優先往下一層節點進入
(一直到最底下才能回頭依序得到各自的l跟r)，
這種優先往深的方向走的方式我們一般稱為
深度優先搜尋(DFS, Depth-First Search)。

寫成虛擬碼如下：

define res
maxPathSum(root){
    res = root.val
    dfs(root)
    return res
}
dfs(n){
    l = (n.left != NIL) ? dfs(n.left) : 0
    r = (n.right != NIL) ? dfs(n.right) : 0
    m = n.val
    m = max(m, l + m, r + m) // 單做為經過點的最大路徑和
    res = max(res, m, l + r + n.val) // m已比過3種可能，故只需再考慮中繼點
    return m
}

在這個虛擬碼當中，我們先考慮左右是否還有連接節點，
有的話就進行dfs往下找出經過點的最大路徑和，沒有的話則補上0；
接著先考慮m的部分，再利用已經比過大小的m來和作為中繼點的狀況比較，
最後和當前最大路徑和相比並更新結果，完整走完所有流程即可得到回傳的答案。

Java的部分，這邊使用了if來作比較，
實測上和一組一組依序使用Math.max來相比並沒有明顯速度上的區別，
讀者可依自己喜好使用。

Java:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int res;
    public int maxPathSum(TreeNode root) {
        res = root.val;
        dfs(root);
        return res;
    }
    public int dfs(TreeNode n) {
        int l = (n.left != null) ? dfs(n.left) : 0;
        int r = (n.right != null) ? dfs(n.right) : 0;
        int m = n.val;
        if (l > r)
            m = Math.max(m, l + m);
        else
            m = Math.max(m, r + m);
        
        if (m > l + r + n.val)
            res = Math.max(res, m);
        else
            res = Math.max(res, l + r + n.val);
        return m;
    }
}

Python的部分，留意呼叫時加上的self.即可，
且max可適用於多個傳入值，比起Java會再方便一點。

Python:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def __init__(self):
        self.res = 0
    
    def maxPathSum(self, root: TreeNode) -> int:        
        self.res = root.val
        self.dfs(root)
        return self.res
    
    def dfs(self, n: TreeNode) -> int:
        l = self.dfs(n.left) if n.left else 0
        r = self.dfs(n.right) if n.right else 0
        m = max(n.val, l + n.val, r + n.val)
        self.res = max(self.res, m, l + r + n.val)
        return m

面試實際可能會遇到的問題：
「時間/空間複雜度？」
(每個節點均會走過一遍，故時間複雜度為O(N)
除了res, l, r, m以外沒有額外的空間了，自行宣告的空間複雜度為O(1)，
但進入遞迴會用到Stack，最大應該是這棵二元樹的高度，
也就是最糟的狀況下可以到O(N)，最好的狀況則是O(logN))

從LeetCode學演算法，我們下次見囉，掰~

下篇預告：
0111. Minimum Depth of Binary Tree (Easy)