Leetcode 113. 총 경로 II(Python3)

1308 단어 python3leetcode
113. 경로 총 II
두 갈래 나무와 목표와 뿌리 노드에서 잎 노드까지의 모든 경로를 찾는 것은 목표와 같은 경로입니다.
설명: 잎 노드는 하위 노드가 없는 노드를 가리킨다.
예: 다음과 같은 두 갈래 트리와 목표 및sum = 22 ,
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

반환:
[
   [5,4,11,2],
   [5,8,4,5]
]
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: List[List[int]]
        """
        res = []
        self.dfs(root,sum,[],res)
        return res
        
    def dfs(self,root,sum,path,res):
        if not root:
            return 
        l,r,val,sum = root.left,root.right,root.val,sum-root.val
        path.append(val)
        if l == None and r == None and sum == 0:
            res.append(list(path))
        self.dfs(l,sum,path,res)
        self.dfs(r,sum,path,res)
        path.pop()

좋은 웹페이지 즐겨찾기