LeetCode|面接問題34.二叉木とある値の経路【剣指Offer】【Python】

LeetCode面接問題34.二叉木とある値の経路【剣指Offer】【Medium】【Python】【遡及】
に質問
スナップ
ツリーと整数を入力し、ツリーのノード値と入力整数のすべてのパスを印刷します.ツリーのルートノードからリーフノードまで下に進むノードがパスを形成します.
例:次のツリーとターゲットとsum=22が与えられます.

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

戻り値:

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

ヒント:

<= 10000

注意:本題はメインステーション113題と同じです.
構想
さかのぼる

       ，    。
        res  。
           。

時間複雑度:O(n),nはツリーノード数である.空間複雑度:O(n),最悪,二叉木は単鎖表に劣化した.
Python 3コード

# 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)
            #     ，        
            path.pop()
        
        recur(root, sum)
        return res

GitHubリンク
Python