【python-lintcode376-树的深度遍历】二叉树的路径和
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【python-lintcode376-树的深度遍历】二叉树的路径和,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1465字,纯文字阅读大概需要3分钟。
内容图文
![【python-lintcode376-树的深度遍历】二叉树的路径和](/upload/InfoBanner/zyjiaocheng/641/6d7537c58dcf4b2e99686457b97265f7.jpg)
给定一个二叉树,找出所有路径中各节点相加总和等于给定 目标值
的路径。
一个有效的路径,指的是从根节点到叶节点的路径。
样例
样例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) #如果该值等于target if 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()
内容总结
以上是互联网集市为您收集整理的【python-lintcode376-树的深度遍历】二叉树的路径和全部内容,希望文章能够帮你解决【python-lintcode376-树的深度遍历】二叉树的路径和所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。