Path Sum II

题目描述

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]
]

解题方法

和Path Sum I一样的做法，只不过在这里stack的tuple再加上目前为止的path，如果找到了就将这个path加到结果里

Solution

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

class Solution(object):
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: List[List[int]]
        """
        if not root:
            return []

        result = []
        stack = []
        stack.append((root, root.val, [root.val]))
        while stack:
            curNode, curSum, curPath = stack.pop()
            if not curNode.left and not curNode.right and curSum == sum:
                result.append(curPath)
            if curNode.left:
                stack.append((curNode.left, curSum + curNode.left.val, curPath + [curNode.left.val]))
            if curNode.right:
                stack.append((curNode.right, curSum + curNode.right.val, curPath + [curNode.right.val]))

        return result

Reference