NC8 二叉树根节点到叶子节点和为指定值的路径

题目描述

给定一个二叉树和一个值sum，请找出所有的根节点到叶子节点的节点值之和等于sum的路径，例如：
给出如下的二叉树，sum=22，

返回
[
[5,4,11,2],
[5,8,9]
]

示例1
输入：
{1,2},1
返回值：
[]

示例2
输入：
{1,2},3
返回值：
[[1,2]]

解题思路

常见的dfs，使用前序遍历即可。当遍历到叶子结点时，算一下路径长度。

Python没有C语言中的变量。在C语言中，变量不止是个名字，它是字节集合并真实存在于内存某个位置上。而在Python中，变量仅仅是指向对象的标签。改动一个标签，其他的标签也会跟着改变。
因此，python复制list的方法为new = old[:]。

解题代码

class Solution:
    def __init__(self):
        self.result_path = []

    def sum(self, nums):
        result = 0
        for i in range(len(nums)):
            result += nums[i]
        return result

    def dfs(self, root, path, sum):
        if not root:
            return
        now_path = path[:]
        now_path.append(root.val)
        result = self.sum(now_path)
        if result == sum:
            if not root.left and not root.right: # 是叶子结点
                self.result_path.append(now_path)
        self.dfs(root.left, now_path, sum)
        self.dfs(root.right, now_path, sum)

    def pathSum(self, root, sum):
        self.dfs(root, [], sum)
        return self.result_path

执行结果

运行时间：56ms
超过90.61% 用Python 3提交的代码
占用内存：7732KB
超过1.69%用Python 3提交的代码