[LeetCode]113 路径总和II

题目描述

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树，以及目标和 sum = 22，

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

将其展开为：

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

# 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, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: List[List[int]]
        """
        if root == None:
            return []
        finals = []
        ans = [root.val]
        dfs(root.val, sum, root, ans, finals)

        return finals

def dfs(cur, sum, node, ans, finals):
    if node.left == None and node.right == None and cur == sum:
        finals.append([i for i in ans])

    if node.left != None:
        ans.append(node.left.val)
        dfs(cur + node.left.val, sum, node.left, ans, finals)
        ans.pop()

    if node.right != None:
        ans.append(node.right.val)
        dfs(cur + node.right.val, sum, node.right, ans, finals)
        ans.pop()