合縱連橫: 從路徑和 理解 DFS+樹型DP 框架的本質。
這篇文章，會帶著大家複習以前學過的DFS框架 結合樹型DP，
並且以路徑和Path Sum的概念與應用為核心，
貫穿一些相關聯的題目，透過框架複現來幫助讀者理解這個演算法框架。
DFS 深度優先搜索框架
def dfs( parameter ):
if base case or stop condition:
# 更新結果
return
for each child node:
# 更新參數，遞回下一層的節點
dfs( updated parameter)
return
如果特化成二元樹中的DFS，往往具有下列形式
def dfs( parameter ):
if base case or stop condition:
# 更新結果
return
# 更新參數，遞回下一層的節點
# 分別是 左子樹 和 右子樹
dfs( updated parameter to left child )
dfs( updated parameter to right child )
return
示意圖
接下來，我們會用這個上面這種框架，貫穿一些同類型，有關聯的題目
(請讀者、或觀眾留意上面的這種 前綴和 框架，之後的解說會反覆出現)
Path Sum - LeetCode 路徑和 I
題目開門見山，直接問是否存在一條從根結點到葉子節點的路徑，
路徑上的節點值總和恰好為targetSum?
共通模式是什麼?
需要累加路徑上的節點總值，等價的說，
從根結點沿路往下扣掉經過節點的值，假如到葉子節點的時候剛好扣完相等，
那麼就存在一條節點值總和為targetSum的路徑。
什麼時候停下來?
當遇到空節點或空樹的時候，可以直接返回False，因為根本沒有路徑存在，一定無解。
當檢查到葉子節點的時候，就停下來，順便檢查targetSum是否剛好扣完相等，
返回答案。
以DFS框架的形式實現演算法，程式碼如下:
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if not root:
return False
if not root.left and not root.right:
return targetSum == root.val
left = self.hasPathSum( root.left, targetSum-root.val )
right = self.hasPathSum( root.right, targetSum-root.val )
return left or right
Path Sum II - LeetCode 路徑和 II
這題延伸推廣，要求把滿足targetSum的路徑給記錄下來。
基本思考邏輯和前一題類似，只是多了一個tracker去記錄符合條件的路徑。
以DFS框架的形式實現演算法，程式碼如下:
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
all_path = []
def dfs(cur, tracker, target):
# Base case: Empty tree or empty node
if not cur:
return
tracker.append( cur.val )
# Base case: Leaf node is pefect matched to targetSum
if not cur.left and not cur.right and target == cur.val:
all_path.append( tracker[::] )
else:
## General cases: keep search left subtree as well as right subtree
dfs(cur.left, tracker , target - cur.val )
dfs(cur.right, tracker , target - cur.val )
tracker.pop()
return
# -------------------------------------------------
dfs(cur=root, tracker=[], target=targetSum)
return all_path
Path Sum III - LeetCode 路徑和 III
這題就比較進階一點。
路徑和系列前兩題都是考從根結點到葉子節點的路徑和。
這題是考區間和，條件變得比較寬鬆。
未必一定要從根結點開始走，只要其中某一段路徑滿足targetSum即可。
這邊同樣會用到以前學過的前綴和計算區間和的觀念:
如果S 和 S - t 存在，
那麼之前肯定存在某個區間(在這題就是路徑)，區間和恰好等於t。
在Tree或者Binary Tree裡面建立DP Table，就是我們這邊所謂的樹型DP。
這題的DP Table紀錄的就是每個前綴和prefix sum的出現次數。
共通模式是什麼?
需要記錄沿途中的每一個前綴和的出現次數，等價的說，
如果當下前綴和為S，而且S - targetSum以前又看過，
那麼這棵樹肯定存在某條路徑，路徑和恰好等於targetSum。
什麼時候停下來?
當遇到空節點或空樹的時候，可以直接返回0，因為根本沒有路徑存在，一定無解。
以DFS框架的形式實現演算法，程式碼如下:
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
prefix_path_sum = defaultdict(int)
prefix_path_sum[0] = 1
def counting( node, s ):
# Base case: empty node or empty tree
if not node:
return 0
# General cases:
# update prefix sum
s += node.val
# If s and s-targeSum exist, then there are some path with tatgetSum exactly.
count = prefix_path_sum[ s - targetSum ]
# update counting of current prefix sum
prefix_path_sum[s] += 1
count += ( counting(node.left, s) + counting(node.right, s) )
# roll back counting of current prefix sum
prefix_path_sum[s] -= 1
return count
# ---------------------------
return counting(node=root, s=0)
結語
好，今天一口氣介紹了最精華的部分，
通用的DFS+樹型DP框架，還有相關的路徑和應用題與演算法建造，
希望能幫助讀者、觀眾徹底理解它的原理，
並且能夠舉一反三，洞察其背後的本質和了解相關的應用領域！
感謝收看囉! 我們下篇文章再見~
