113-路径总和 II

有空一起学习 2018年12月14日17:56:54 发表评论
文章最后编辑于:2019-12-14 17:59:21

来源:力扣(LeetCode)

链接:113. 路径总和 II

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

一、题目描述

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

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

示例:

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

返回:

二、题解

说明:

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

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

算法:

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

代码:

113-路径总和 II

复杂度分析:

  • 时间复杂度:访问每个节点一次,时间复杂度为O(N) ,其中N是节点个数。
  • 空间复杂度:需要用到两个数组,其中一个是保存结果的数组可不算入空间占用,另外一个保存路径的临时数组最坏情况下(树是一条线,即类似链表的时候)占用O(N) ,平均和最优情况下(树是平衡树)占用O(log(N))。
本文共执行66次查询,耗时0.370秒!
有空一起学习

发表评论

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