【python-lintcode376-树的深度遍历】二叉树的路径和
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【python-lintcode376-树的深度遍历】二叉树的路径和，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1301字，纯文字阅读大概需要2分钟。
内容图文
给定一个二叉树，找出所有路径中各节点相加总和等于给定 目标值 的路径。
一个有效的路径，指的是从根节点到叶节点的路径。
样例
样例1:
输入:
{1,2,4,2,3}
5
输出: [[1, 2, 2],[1, 4]]
说明:
这棵树如下图所示：
1
/ 2 4
/ 2 3
对于目标总和为5，很显然1 + 2 + 2 = 1 + 4 = 5
样例2:
输入:
{1,2,4,2,3}
3
输出: []
说明:
这棵树如下图所示：
1
/ 2 4
/ 2 3
注意到题目要求我们寻找从根节点到叶子节点的路径。
1 + 2 + 2 = 5, 1 + 2 + 3 = 6, 1 + 4 = 5
这里没有合法的路径满足和等于3.
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class
Solution:
"""
@param: root: the root of binary tree
@param: target: An integer
@return: all valid paths
"""
def
binaryTreePathSum(self, root, target):
#
write your code here
global
res
#
保存结果
res=[]
#临时数组
tmp=[]
self.pathSum(res,tmp,root,target)
return res
def pathSum(self,res,tmp,root,target):
if root == None:
return#首先将当前节点的值加入到tmp中 tmp.append(root.val)
#如果当前节点没有左右孩子，说明是叶子节点if root.left == None and root.right == None:
#计算根节点到叶子节点的值
s = sum(tmp)
#如果该值等于targetif s == target:
#这里需要拷贝一份tmp，再加入到结果中
newtmp=tmp[:]
res.append(newtmp)
#如果有左孩子if root.left!=None:
self.pathSum(res,tmp,root.left,target)
#如果遍历到叶子节点了，且不符合sum(tmp)==target，则最后面的节点出栈 tmp.pop()
#如果有右孩子if root.right!=None:
self.pathSum(res,tmp,root.right,target)
#如果遍历到叶子节点了，且不符合sum(tmp)==target，则最后面的节点出栈 tmp.pop()
原文：https://www.cnblogs.com/xiximayou/p/12396986.html
内容总结
以上是互联网集市为您收集整理的【python-lintcode376-树的深度遍历】二叉树的路径和全部内容，希望文章能够帮你解决【python-lintcode376-树的深度遍历】二叉树的路径和所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】