iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 19
1
Software Development

從LeetCode學演算法系列 第 19

[Day 19] 從LeetCode學演算法 - 0124. Binary Tree Maximum Path Sum (Hard)

目標:
這題主要目的在於進階探索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)


上一篇
[Day 18] 從LeetCode學演算法 - 0094. Binary Tree Inorder Traversal (Medium)
下一篇
[Day 20] 從LeetCode學演算法 - 0111. Minimum Depth of Binary Tree (Easy)
系列文
從LeetCode學演算法30

尚未有邦友留言

立即登入留言