深圳宝安高端网站建设公司,抖音运营方案详细,百度站长对网站会有影响吗,网站建网站建设网站站网站Python3解题#xff1a;二叉树路径总和问题原题 https://leetcode-cn.com/problems/path-sum-ii/
给定一个二叉树和一个目标和#xff0c;找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例: 给定如下二叉树#xff…
Python3解题二叉树路径总和问题原题 https://leetcode-cn.com/problems/path-sum-ii/
给定一个二叉树和一个目标和找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例: 给定如下二叉树以及目标和 sum 22
5/ \4 8/ / \11 13 4/ \ / \7 2 5 1返回:
[[5,4,11,2],[5,8,4,5]
]解题
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val x
# self.left None
# self.right Noneclass Solution:def pathSum(self, root: TreeNode, sum: int) - List[List[int]]:self.res [] # 存放结果self.dp(root, [], sum) # 解题return self.res# 用动态规划算法把大问题分解成左右两个小问题自顶向下def dp(self, node, arr, rest):if node None:returnval node.valrest - valif rest 0 and node.left None and node.right None:self.res.append(arr [val])returnself.dp(node.left, arr [val], rest) # 左子树self.dp(node.right, arr [val], rest) # 右子树
