這篇文章,會帶著大家複習以前學過的DFS框架 結合樹型DP,
並且以路徑和Path Sum的概念與應用為核心,
貫穿一些相關聯的題目,透過框架複現來幫助讀者理解這個演算法框架。
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
接下來,我們會用這個上面這種框架,貫穿一些同類型,有關聯的題目
(請讀者、或觀眾留意上面的這種 前綴和 框架,之後的解說會反覆出現)
題目開門見山,直接問是否存在一條從根結點到葉子節點的路徑,
路徑上的節點值總和恰好為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
這題延伸推廣,要求把滿足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
這題就比較進階一點。
路徑和系列前兩題都是考從根結點到葉子節點的路徑和。
這題是考區間和,條件變得比較寬鬆。
未必一定要從根結點開始走,只要其中某一段路徑滿足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框架,還有相關的路徑和應用題與演算法建造,
希望能幫助讀者、觀眾徹底理解它的原理,
並且能夠舉一反三,洞察其背後的本質和了解相關的應用領域!
感謝收看囉! 我們下篇文章再見~