113-路径总和 II

马谦马谦马谦
马谦马谦马谦
马谦马谦马谦
615
文章
12
评论
2018年12月14日17:56:54 评论

来源:力扣(LeetCode)

链接:113. 路径总和 II

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

一、题目描述

给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明:叶子节点是指没有子节点的节点。

示例:

给定如下二叉树,以及目标和 sum = 22:

返回:

二、题解

说明:

此题是112. 路径总和Ⅰ的升级版(题解参考:113-路径总和Ⅰ),相对于第一题来说,有以下两点不通:

  1. 题Ⅰ只需要判断存在即可,该题需要找到所有可能的结果。
  2. 找到所有结果的同时,该题还需要保存所有的路径。

算法:

递归+深搜遍历所有的树节点,每遍历一个节点除了计算sum是否满足条件以外,还要记录下该节点。当遇到满足条件的叶节点,把当前路径加到结果中去。需要利用到两个辅助的数组。

代码:

113-路径总和 II

复杂度分析:

  • 时间复杂度:访问每个节点一次,时间复杂度为O(N) ,其中N是节点个数。
  • 空间复杂度:需要用到两个数组,其中一个是保存结果的数组可不算入空间占用,另外一个保存路径的临时数组最坏情况下(树是一条线,即类似链表的时候)占用O(N) ,平均和最优情况下(树是平衡树)占用O(log(N))。
马谦马谦马谦
  • 本文由 发表于 2018年12月14日17:56:54
  • 转载请务必保留本文链接:https://www.dyxmq.cn/program/algorithms/path-sum-ii.html
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: