【python-leetcode113-树的深度遍历】路径总和Ⅱ

发布时间：2020-12-20 09:54:23 所属栏目：Python 来源：网络整理

导读：对应着lintcode376题。 ? 给定一个二叉树，找出所有路径中各节点相加总和等于给定目标值的路径。一个有效的路径，指的是从根节点到叶节点的路径。样例样例1: 输入: {1,2,4,3} 5 输出: [[1,2],[1,4]] 说明: 这棵树如下图所示： 1 / 2 4 / 2 3 对于目

对应着lintcode376题。

给定一个二叉树，找出所有路径中各节点相加总和等于给定目标值的路径。

一个有效的路径，指的是从根节点到叶节点的路径。

样例
样例1:

输入:
{1,2,4,3}
5
输出: [[1,2],[1,4]]
说明:
这棵树如下图所示：
1
/
2 4
/
2 3
对于目标总和为5，很显然1 + 2 + 2 = 1 + 4 = 5
样例2:

输入:
{1,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,target)
        return res
     pathSum(self,res,1)">if root == None:
            return
        首先将当前节点的值加入到tmp中
        tmp.append(root.val)
        如果当前节点没有左右孩子，说明是叶子节点
        if root.left == None and root.right ==计算根节点到叶子节点的值
            s = sum(tmp)
            如果该值等于target
            if s == target:
                这里需要拷贝一份tmp，再加入到结果中
                newtmp=tmp[:]
                res.append(newtmp)
        如果有左孩子
        if root.left!=None:
            self.pathSum(res,root.left,target)
            如果遍历到叶子节点了，且不符合sum(tmp)==target，则最后面的节点出栈
            tmp.pop()
        如果有右孩子
        if root.right!=            tmp.pop()

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!