美文网首页Leetcode
113. Path Sum II

113. Path Sum II

作者: oo上海 | 来源:发表于2016-07-25 07:26 被阅读11次

    113. Path Sum II

    题目:

    https://leetcode.com/problems/path-sum-ii/

    tag : DFS

    难度 : Medium

    注意宁愿写几次curList + [root.val] 也不要直接传一个list进去,因为list pass by reference的亏已经吃过了

    # 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]]
            """
            result = []
            self.auxPathSum(root,sum,[],result)
            return result
            
        def auxPathSum(self, root, sum, curList, curLists):
            if root == None:
                return
            sum -= root.val
            if sum == 0 and (root.left == None and root.right == None):
                curLists.append(curList + [root.val])
                return 
            if root.left != None:
                self.auxPathSum(root.left, sum - root.val, curList + [root.val],curLists)
            if root.right != None:
                self.auxPathSum(root.right, sum - root.val, curList + [root.val],curLists)
    

    相关文章

      网友评论

        本文标题:113. Path Sum II

        本文链接:https://www.haomeiwen.com/subject/mqegjttx.html