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

先简单回顾一下，今天预计分析的题目： 112. Path Sum

题目连结：https://leetcode.com/problems/path-sum/

题目叙述：

• 会给一个二元树与目标总和
• 要找一个从 root 到 leaf 的路径，加总为目标总和
  

测资的 Input/Output

• 若找到 root 到 leaf 的路径相加的总和为目标值，则回传 true，反之，回传 false
  

DFS 递回 解法

1. 判断是否有 Node，若无则回传 False

if root is None: return False

2. 用递回方式实作 DFS 走访这棵树：首先计算目前的加总

newSum = prevSum + node.val

3. 紧接着写终止条件：若是此点为 leaf，检查目前加总是否等於 targetSum

if node.left is None and node.right is None: return newSum == targetSum

4. 若此点非叶子，若有左 child，则往左 child 走，若 return True 回来，表示有找到符合加总的路径，便无需往下做，跟着回传 True

if node.left is not None and dfsFindPath(node.left, newSum): return True

5. 若此点非叶子，若有右 child，则往右 child 走，若 return True 回来，表示有找到符合加总的路径，便无需往下做，跟着回传 True

if node.right is not None and dfsFindPath(node.right, newSum): return True

6. 若以上情况都没有，则回传 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)]

3. 接下来开始迭代，当 stack 中还有资料，就取一个 node 出来。

node, prevSum = stack.pop()

4. 走访当前节点，计算新的总和

newSum = prevSum + node.val

5. 若当前节点为叶子，且总和符合目标值，则回传 True

if node.left is None and node.right is None and newSum == targetSum: return True

6. 若当前节点不为叶子：

   1. 若左侧 child 存在，则将其加入 stack 中，待稍後进行走访。

   if node.left is not None: stack.append((node.left, newSum))
   

   2. 若右侧 child 存在，则将其加入 stack 中，待稍後进行走访。

   if node.right is not None: stack.append((node.right, newSum))
   

7. 若完整迭代完毕，表示没有找到相符的 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