113. Path Sum II

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

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()

Information

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

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

  • Tags: Tree, Depth-first Search