pydata

Keep Looking, Don't Settle

leetcode 113. path sum

113. Path Sum II

112. Path Sum

题目大意: Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

解题思路:把当前要找的sum减去node节点的值作为新的sum的值,然后递归求解左指数,递归求解右指数,直到leaf节点,判断当前剩下的sum跟leaf节点的.val是不是相同。

def pathSum(self, root, sum):
    if not root:
        return []
    self.res = []
    def dfs(node, sum, temp):
        if not node:
            return []
        if not node.left and not node.right:
            if node.val - sum == 0:
                temp.append(node.val)
                self.res.append(temp[:])
                temp.pop()
        temp.append(node.val)
        sum -= node.val
        dfs(node.left, sum, temp)
        dfs(node.right, sum, temp)
        temp.pop()
    dfs(root, sum, [])
    return self.res