圖論應用題: 樹的路徑總和 Path Sum_Leetcode #112

Boxed Water Is Better null on Unsplash

題目敘述

題目會給定一顆二元樹的根結點Root node，和指定的目標值targetSum。

問我們能不能從二元樹裡面找到一條從根結點到葉子結點的路徑，其路徑上的節點值總和恰好為targetSum?

可以的話，返回True。

無解的話，返回False。

題目的原文敘述

測試範例

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with the target sum is shown.

Example 2:

Input: root = [1,2,3], targetSum = 5
Output: false
Explanation: There two root-to-leaf paths in the tree:
(1 --> 2): The sum is 3.
(1 --> 3): The sum is 4.
There is no root-to-leaf path with sum = 5.

Example 3:

Input: root = [], targetSum = 0
Output: false
Explanation: Since the tree is empty, there are no root-to-leaf paths.

請注意，空樹對應到的是無解喔，要返回False​

約束條件

Constraints:

• The number of nodes in the tree is in the range [0, 5000].

結點總數目介於0~5000之間。

請留意邊界條件的處理，題目有可能給我們一顆空樹。

• -1000 <= Node.val <= 1000

節點值都介於 負一千 ~ 正一千之間。

• -1000 <= targetSum <= 1000

目標值targetSum 一定介於 負一千 ~ 正一千 之間。

演算法

題目已經說從二元樹裡面，看看能不能找到一條從根結點到葉子結點的路徑，其路徑上的節點值總和恰好為targetSum?

那就順著題意走，從Root node根結點出發，從上往下走，每經過一個節點，就把targetSum減去對應的結點值node.val，假如到葉子結點的時候，targetSum剛好扣完，那就表示有解，返回True。

否則，假如都找不到，代表無解，返回False。

程式碼 DFS從上到下深度優先搜索每個結點

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        
        ## Base case: Empty tree or empty node
        if not root:
            return False
        
        ## Base case
        if not root.left and not root.right:
            
            # we have the path with targetSum
            return targetSum == root.val
        
        ## General case:
        return self.hasPathSum(root.left, targetSum - root.val) or \
                self.hasPathSum(root.right, targetSum - root.val)

複雜度分析 DFS從上到下深度優先搜索每個結點

時間複雜度:

從根結點開始，探索整顆樹，每個結點最多拜訪一次，所需時間為O(n)。

空間複雜度:

從根結點開始，探索整顆樹，遞迴深度最深為n，發生在整顆樹向左歪斜或向右歪斜的時候，所需recursion call stack最深為O(n)。

程式碼 BFS從上到下 廣度優先，逐層往下探索每個結點

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        
        # Base case: empty tree 
        if not root:
            return False

        # BFS Queue, starting from root node with given targetSum
        bfs_q = deque([ (root, targetSum)])

        # Launch BFS aka level-order traversal from root node
        while bfs_q:

            cur, target = bfs_q.popleft()            

            # We've reached leaf node, and my value equals to target value
            if not cur.left and not cur.right and target == cur.val:
                return True
            
            # Update target value for next level
            target -= cur.val

            # Push children into BFS queue
            cur.left and bfs_q.append( (cur.left, target) )
            cur.right and bfs_q.append( (cur.right, target) )

        return False

複雜度分析 BFS從上到下 廣度優先，逐層往下探索每個結點

時間複雜度:

從根結點開始，探索整顆樹，每個結點最多拜訪一次，所需時間為O(n)。

空間複雜度:

從根結點開始，探索整顆樹，BFS Queue長度最長為O(n/2)，發生最後一層而且樹全滿的時候，所需空間最大為O(n/2) = O(n) 係數可省略。

關鍵知識點

順著題意走，從Root node根結點出發，從上往下走，每經過一個節點，就把targetSum減去對應的結點值node.val，假如到葉子結點的時候，targetSum剛好扣完，那就表示有解，返回True。

否則，代表無解，返回False。

Reference:

[1] Path Sum_Python O(n) DFS solution

[2] Path Sum_Python O(n) BFS solution