【LeetCode with Python】 113. Path Sum II

题目

原题页面:https://leetcode.com/problems/path-sum-ii/
本文地址:http://leetcode.xnerv.wang/path-sum-ii/
题目类型:Tree, Depth-first Search
难度评价:Medium
类似题目:(E) Path Sum, (E) Binary Tree Paths

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差不多,不过要记录一下所有可行解。


代码

class Solution:

    def __init__(self):
        self.paths = [ ]

    def doPathSum(self, root, total, sum, path):
        if None == root.left and None == root.right:
            path.append(root.val)
            result = (sum == (total + root.val))
            if True == result:
                self.paths.append(path)

        left= False
        right = False
        if None != root.left:
            new_path = path[:]
            new_path.append(root.val)
            left = self.doPathSum(root.left, total + root.val, sum, new_path)
        if None != root.right:
            new_path = path[:]
            new_path.append(root.val)
            right = self.doPathSum(root.right, total + root.val, sum, new_path)
        return left or right

    # @param root, a tree node
    # @param sum, an integer
    # @return a list of lists of integers
    def pathSum(self, root, sum):
        if None == root:
            return [ ] ###
        result = self.doPathSum(root, 0, sum, [ ])
        return self.paths

results matching ""

    No results matching ""