python实现leetcode之113. 路径总和 II

解题思路

深度优先
将达到叶子结点并且刚好满足路径和为sum的路径path作为返回值之一
所有满足条件的路径合并在一起就是返回值

113. 路径总和 II

代码

# 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]]
        """
        if not root: return []
        return find_sum(root, sum, [])


def find_sum(tree, s, path):
    ans = []
    if is_leaf(tree):
        if tree.val == s:
            ans.append([*path, tree.val])
    else:
        if tree.left:
            ans.extend(find_sum(tree.left, s-tree.val, [*path, tree.val]))
        if tree.right:
            ans.extend(find_sum(tree.right, s-tree.val, [*path, tree.val]))
    return ans


def is_leaf(node):
    return not node.left and not node.right