113. Path Sum II

Information

  • Diffculty: Medium

  • Created: 2020-01-11 16:31:28

  • Last Motified: 2020-01-11 16:31:28

  • Tags: Tree, Depth-first Search

Intuition

The idea is almost the same as 112. Path Sum. One more requirement is that we need to return all the paths from the root node to the leaf node who fits the requirement.

Solution

# 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: TreeNode, s: int) -> List[List[int]]:
        self.stack = []
        self.result = []
        self._helper(root, s)
        return self.result

    def _add_path(self):
        self.result.append(self.stack[:])

    def _helper(self, node, s):
        if node is None:
            return
        self.stack.append(node.val)
        s -= node.val
        if node.left == node.right == None:
            if s == 0:
                self._add_path()
        self._helper(node.left, s)
        self._helper(node.right, s)
        self.stack.pop()