從LeetCode學演算法

0124. Binary Tree Maximum Path Sum (Hard)

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

1
Input: [1,2,3]

1
Output: 6

Example 2

1
Input: [-10,9,20,null,null,15,7]

1
Output: 42

分析/解題

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

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

開始囉！

如果我們多拿幾組節點來進行觀察，會發現從一個節點要走到另一個節點，要先經過它們最低的共同祖先節點(這邊指從雙方往上走第一個碰頭的位置)，再走下來才行。
以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)。

寫成虛擬碼如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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

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

Python

面試實際可能會遇到的問題

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

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