剑指 Offer 34. 二叉树中和为某一值的路径 - leetcode 剑指offer系列
发布日期:2021-06-29 07:12:10
浏览次数:4
分类:技术文章
本文共 2521 字,大约阅读时间需要 8 分钟。
题目难度: 中等
今天继续更新剑指 offer 系列, 这道题挺经典的, 这里提供递归和迭代两种方案供大家参考
老样子晚上 6 点 45 分准时更新公众号 每日精选算法题, 大家记得关注哦~ 另外在公众号里回复 offer 就能看到剑指 offer 系列当前连载的所有文章了
题目描述
输入一棵二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
- 节点总数 <= 10000
题目样例
示例
输入
给定如下二叉树,以及目标和 sum = 22,
5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1
输出
[ [5,4,11,2], [5,8,4,5]]
题目思考
- 如何用递归思路来解决? 需要保存哪些信息?
- 可以用前几天的 BFS 解决吗?
解决方案
方案 1
思路
- 首先考虑递归思路
- 这道题很适合用 DFS 来做, 因为在遍历的过程中可以保存路径中的节点, 以及当前和之类的信息
- 最后到叶子节点时只需要判断当前和是否等于目标, 是的话将路径加入结果中即可
- 递归出口自然就是当前节点是叶子节点了
- 如果不是叶子节点的话, 就递归调用非空的子节点, 将其值加入和中, 节点本身加入路径中即可
- 特别注意的是, 由于题目没有说节点值非负, 所以必须老老实实走到叶子节点才知道和是否等于目标. 不然如果节点值都是非负数的话, 就可以在当前和大于目标时直接返回了, 之后的和只可能更大, 肯定不满足条件
复杂度
- 时间复杂度
O(N)
- 每个节点只需要遍历一次
- 空间复杂度
O(N^2)
- 递归的栈的消耗是 N, 然后每个递归调用里面又要分配 N 个节点的路径
代码
class Solution: def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]: if not root: return [] res = [] def dfs(node, path, cur): if cur == sum and not node.left and not node.right: # 当前是叶子节点, 且和正好等于目标, 将路径加入结果中 res.append(path) if node.left: # 递归遍历非空左子节点 dfs(node.left, path + [node.left.val], cur + node.left.val) if node.right: # 递归遍历非空右子节点 dfs(node.right, path + [node.right.val], cur + node.right.val) # 注意初始的路径以及和 dfs(root, [root.val], root.val) return res
方案 2
思路
- 如果限制只能用迭代的话, 就不能用 DFS 了
- BFS 就是迭代, 但回忆之前的几种 BFS 方案 (
剑指 Offer 32
), 都只是存了节点本身, 我们如何把路径以及路径和关联起来呢? - 做法也很简单, 既然需要存额外信息, 我们就把队列的内容改造一下, 存成
(节点, 路径, 当前和)
三元组, 然后添加子节点的时候附带上对应路径以及当前和 - 这样如果当前节点是叶子节点的话, 只需要比较当前和与目标即可
复杂度
- 时间复杂度
O(N)
- 每个节点只需要遍历一次
- 空间复杂度
O(N^2)
- 队列需要存 N 个三元组, 每个元组中的路径又包含 N 个节点
代码
class Solution: def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]: if not root: return [] # 初始化根节点/路径/当前和 q = [(root, [root.val], root.val)] res = [] for t in q: node, path, sm = t if not node.left and not node.right and sm == sum: # 当前是叶子节点, 且和正好等于目标, 将路径加入结果中 res.append(path) if node.left: # 将非空左子节点/路径/当前和加入队列 q.append( (node.left, path + [node.left.val], sm + node.left.val)) if node.right: # 将非空右子节点/路径/当前和加入队列 q.append( (node.right, path + [node.right.val], sm + node.right.val)) return res
大家可以在下面这些地方找到我~😊
我的公众号: 每日精选算法题, 欢迎大家扫码关注~😊
转载地址:https://blog.csdn.net/zjulyx1993/article/details/107444085 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
不错!
[***.144.177.141]2024年04月25日 01时36分35秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
七牛 PHP 文件管理
2019-04-29
汽车OBD产品
2019-04-29
短网址dwz.cn批量注册
2019-04-29
dcloud mui html5plus 5+sdk
2019-04-29
不要驱动,简单粗暴的用树莓派驱动USB打印机
2019-04-29
树莓派摄像头模块应用程序文档翻译[转]
2019-04-29
ffmpeg+ffserver搭建流媒体服务器
2019-04-29
使用 WebSockets 进行 HTML5 视频直播
2019-04-29
用redis实现支持优先级的消息队列
2019-04-29
基于WebRTC的多人视频会议
2019-04-29
蓝牙BR/EDR和Bluetooth Smart的十大重要区别
2019-04-29
树莓派WIFI设置
2019-04-29
树莓派摄像头及视频
2019-04-29
树莓派杂项
2019-04-29
SVG操作
2019-04-29
阿里云ECS使用
2019-04-29
VC6 C/CPP操作ORACLE数据库 clilib方案
2019-04-29
single修改版
2019-04-29
IIS 多站点HTTPS加密及自动http跳转到https
2019-04-29
NGINX重启HTTPS站点要Enter PEM pass phrase输入密码
2019-04-29