首页 > 试题广场 >

二叉树中和为某一值的路径(三)

[编程题]二叉树中和为某一值的路径(三)
  • 热度指数：27730 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个二叉树root和一个整数值 sum ，求该树有多少路径的的节点值之和等于 sum 。
1.该题路径定义不需要从根节点开始，也不需要在叶子节点结束，但是一定是从父亲节点往下到孩子节点
2.总节点数目为n
3.保证最后返回的路径个数在整形范围内(即路径个数小于231-1)

数据范围:



假如二叉树root为{1,2,3,4,5,4,3,#,#,-1}，sum=6，那么总共如下所示，有3条路径符合要求

示例1

输入

{1,2,3,4,5,4,3,#,#,-1},6

输出

3

说明

如图所示，有3条路径符合
示例2

输入

{0,1},1

输出

2
示例3

输入

{1,#,2,#,3},3

输出

2

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
Python3
liangzhengjie头像 liangzhengjie
感觉不是那么完美的解法 
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @param sum int整型 
# @return int整型
#
class Solution:
    def FindPath(self , root: TreeNode, sum: int) -> int:
        # write code here
        collection = []
        self.traverse1(root, collection)

        res = 0
        for i in collection:
            for j in i:
                if j == sum:
                    res += 1

        return res

    def traverse1(self, root, collection):
        if root is None:
            return

        tmp = []
        self.traverse2(root, 0, tmp)
        collection.append(tmp)
        
        self.traverse1(root.left, collection)
        self.traverse1(root.right, collection)

    def traverse2(self, root, now_res, num_arr):
        if root is None:
            return

        num_arr.append(now_res + root.val)
        self.traverse2(root.left, now_res + root.val, num_arr)
        self.traverse2(root.right,  now_res + root.val, num_arr)


编辑于 2024-04-23 21:53:15 回复(0)
Python3
牛客862270258号头像 牛客862270258号 
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param root TreeNode类
# @param sum int整型
# @return int整型
#
class Solution:
    def FindPath(self, root: TreeNode, sum: int) -> int:
        # write code here
        if not root: return 0
        # 每一个结点统计开始时，初始化累加器
        self.count = 0
        return self.dfs(root, sum) + \
               self.FindPath(root.left, sum) + \
               self.FindPath(root.right, sum)

    # 对结点进行深度遍历，遍历过程中遇到和为sum的路径，累加器count加1
    count = 0
    def dfs(self, root, sum):
        if not root:
            return 0
        if sum == root.val:
            self.count += 1
        self.dfs(root.left, sum - root.val)
        self.dfs(root.right, sum - root.val)
        # 返回累加器的值
        return self.count

发表于 2023-07-05 11:25:59 回复(0)
提交观点

问题信息

树
上传者：牛客301499号
难度：
3条回答 1968浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号