iT邦幫忙

2021 iThome 鐵人賽

DAY 23
0
自我挑戰組

【帶你輕鬆入門演算法-Leetcode】系列 第 23

【第二十三天 - DFS 題目分析】

  • 先簡單回顧一下,今天預計分析的題目: 112. Path Sum

  • 題目連結:https://leetcode.com/problems/path-sum/

  • 題目敘述:

    • 會給一個二元樹與目標總和
    • 要找一個從 root 到 leaf 的路徑,加總為目標總和
      https://ithelp.ithome.com.tw/upload/images/20210923/20140592Kxvan8qpyj.png
  • 測資的 Input/Output

    • 若找到 root 到 leaf 的路徑相加的總和為目標值,則回傳 true,反之,回傳 false
      https://ithelp.ithome.com.tw/upload/images/20210923/201405920ev5IKCxXL.png

    https://ithelp.ithome.com.tw/upload/images/20210923/20140592LHuGcD3kne.png

  • DFS 遞迴 解法

    1. 判斷是否有 Node,若無則回傳 False
    if root is None: return False
    
    1. 用遞迴方式實作 DFS 走訪這棵樹:首先計算目前的加總
    newSum = prevSum + node.val
    
    1. 緊接著寫終止條件:若是此點為 leaf,檢查目前加總是否等於 targetSum
    if node.left is None and node.right is None: return newSum == targetSum
    
    1. 若此點非葉子,若有左 child,則往左 child 走,若 return True 回來,表示有找到符合加總的路徑,便無需往下做,跟著回傳 True
    if node.left is not None and dfsFindPath(node.left, newSum): return True
    
    1. 若此點非葉子,若有右 child,則往右 child 走,若 return True 回來,表示有找到符合加總的路徑,便無需往下做,跟著回傳 True
    if node.right is not None and dfsFindPath(node.right, newSum): return True
    
    1. 若以上情況都沒有,則回傳 False
    return False
    
    • 完整程式碼如下:
    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, val=0, left=None, right=None):
    #         self.val = val
    #         self.left = left
    #         self.right = right
    class Solution:
        def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
            if root is None: return False
    
            def dfsFindPath(node, prevSum):
                newSum = prevSum + node.val
    
                if node.left is None and node.right is None: return newSum == targetSum
                if node.left is not None and dfsFindPath(node.left, newSum): return True
                if node.right is not None and dfsFindPath(node.right, newSum): return True
                return False
    
            return dfsFindPath(root, 0)
    
  • DFS 迭代解法

    1. 若用迭代實作 DFS,我們需要準備一個 stack,用來紀錄走訪的順序。
    2. 首先,先將起點放入 stack 中,同時我們需要紀錄走訪前的加總狀態,才能接續走訪 children。
    stack = [(root, 0)]
    
    1. 接下來開始迭代,當 stack 中還有資料,就取一個 node 出來。
    node, prevSum = stack.pop()
    
    1. 走訪當前節點,計算新的總和
    newSum = prevSum + node.val
    
    1. 若當前節點為葉子,且總和符合目標值,則回傳 True
    if node.left is None and node.right is None and newSum == targetSum: return True
    
    1. 若當前節點不為葉子:

      1. 若左側 child 存在,則將其加入 stack 中,待稍後進行走訪。
      if node.left is not None: stack.append((node.left, newSum))
      
      1. 若右側 child 存在,則將其加入 stack 中,待稍後進行走訪。
      if node.right is not None: stack.append((node.right, newSum))
      
    2. 若完整迭代完畢,表示沒有找到相符的 path,回傳 False

    return False
    

    完整程式碼如下:

    class Solution:
        def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
            if root is None: return False
    
            stack = [(root, 0), ]
            while stack:
                node, prevSum = stack.pop()
                newSum = prevSum + node.val
    
                if node.left is None and node.right is None and newSum == targetSum: return True
                if node.left is not None: stack.append((node.left, newSum))
                if node.right is not None: stack.append((node.right, newSum))
    
            return False
    

上一篇
【第二十二天 - DFS 介紹】
下一篇
【第二十四天 - Floyd-Warshall介紹】
系列文
【帶你輕鬆入門演算法-Leetcode】30

尚未有邦友留言

立即登入留言