LeetCode: 113. Path Sum II

题目

原题地址：https://leetcode.com/problems/path-sum-ii/

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where each path's sum equals targetSum.

A leaf is a node with no children.

Example 1:

image1

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]

Example 2:

image2

Input: root = [1,2,3], targetSum = 5
Output: []

Example 3:

Input: root = [1,2], targetSum = 0
Output: []

Constraints:

  • The number of nodes in the tree is in the range [0, 5000].
  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000

解法

这个题跟 112. Path Sum 的区别是需要找到所有符合条件的 path ，并返回这些 path 上的节点组成的列表。

所以，需要在查找的过程中记录沿途经过的节点的值， 在找到符合条件的 leaf 节点的时候将沿途的节点值收集并保存起来。

这个思路的 Python 代码类似下面这样：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def __init__(self):
        self.paths = []
        self.curr = []

    def pathSum(self, root, targetSum):
        if root is None:
            return self.paths

        if root.left is None and root.right is None:
            if root.val == targetSum:
                curr = self.curr[:]
                curr.append(root.val)
                self.paths.append(curr)
            return self.paths

        self.curr.append(root.val)
        new_sum = targetSum - root.val
        self.pathSum(root.left, new_sum)
        self.pathSum(root.right, new_sum)

        self.curr.pop()

        return self.paths

Comments