首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
备考首页
>
数据结构
>
树
95
编程题
95
/
123
给定一个二叉树root和一个值 sum ,判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。
1.
该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
2.
叶子节点是指没有子节点的节点
3.
路径只能从父节点到子节点,不能从子节点到父节点
4.总节点数目为n
例如:
给出如下的二叉树,
,
返回true,因为存在一条路径
的节点值之和为 22
数据范围:
1.树上的节点数满足
2.每 个节点的值都满足
要求:
空间复杂度
,时间复杂度
进阶:空间复杂度
,时间复杂度
参考答案
dfs,一边遍历一边把根到当前节点的路径和存一下,这样就能继续找下一个节点。
纠错
收藏
查看讨论
1
...
90
91
92
93
94
95
96
97
98
99
100
...
123
跳转到
确 定
上一题
下一题
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题