文章

LeetCode Path Sum II

Problem

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

For example: Given the below binary tree and sum = 22,

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

return

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

Path Sum问题的进一步,不仅仅是判断是否存在路径,而是找出所有的路径。

Python 实现

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
'''
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:
Given the below binary tree and sum = 22,
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
return
[
   [5,4,11,2],
   [5,8,4,5]
]
'''


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

# author li.hzh 2017-11-29 23:34
class Solution:
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype:
         List[List[int]]
        """
        result = []
        if root is None:
            return result
        cur_val = root.val
        sub_sum = sum - cur_val
        if root.left is None and root.right is None and sub_sum == 0:
            return [[cur_val]]
        left_result = []
        if root.left is not None:
            left_result = self.pathSum(root.left, sub_sum)
        if root.right is not None:
            left_result.extend(self.pathSum(root.right, sub_sum))
        for path in left_result:
            path.insert(0, cur_val)
            result.append(path)
        return result


from my.leetcode.TreeNode import TreeNode

tree = TreeNode(1)
one_left = TreeNode(2)
one_right = TreeNode(2)
tree.left = one_left
tree.right = one_right
one_left.left = TreeNode(3)
one_left.right = TreeNode(3)
one_right.left = TreeNode(3)
one_right.right = TreeNode(3)
print(Solution().pathSum(tree, 6))

分析

思路依然是递归,只是这次把路径保存起来即可。

本文由作者按照 CC BY 4.0 进行授权