LeetCode 面試題34. 二叉樹中和為某一值的路徑【劍指Offer】【Medium】【Python】【回溯】

問題

力扣

輸入一棵二叉樹和一個整數(shù)，打印出二叉樹中節(jié)點值的和為輸入整數(shù)的所有路徑。從樹的根節(jié)點開始往下一直到葉節(jié)點所經(jīng)過的節(jié)點形成一條路徑。

示例:
給定如下二叉樹，以及目標和 sum = 22，

          5
         / \
        4   8
       /   / \
      11  13  4
     /  \    / \
    7    2  5   1

返回:

[
   [5,4,11,2],
   [5,8,4,5]
]

提示：

1. 節(jié)點總數(shù) <= 10000

注意：本題與主站 113 題 相同。

思路

回溯

先序遍歷二叉樹，記錄路徑。
符合條件的加入 res 中。
回溯記得要刪除當前節(jié)點。

時間復雜度: O(n)，n 為二叉樹節(jié)點個數(shù)。
空間復雜度: O(n)，最壞情況，二叉樹退化成單鏈表。

Python3代碼

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        res, path = [], []

        # 先序遍歷：根左右
        def recur(root, target):
            if not root:
                return
            
            path.append(root.val)
            target -= root.val
            # 找到路徑
            if target == 0 and not root.left and not root.right:
                res.append(list(path))  # 復制了一個 path 加入到 res 中，這樣修改 path 不影響 res
            recur(root.left, target)
            recur(root.right, target)
            # 向上回溯，需要刪除當前節(jié)點
            path.pop()
        
        recur(root, sum)
        return res

GitHub鏈接

Python