112-路径总和

马谦马谦马谦
马谦马谦马谦
马谦马谦马谦
615
文章
12
评论
2018年9月4日18:51:46 评论

作者:LeetCode

链接:112. 路径总和

来源:力扣(LeetCode)

著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

一、题目描述

给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。

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

示例:

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

返回true, 因为存在目标和为 22 的根节点到叶子节点的路径5->4->11->2

二、题解

2.1 dfs深搜(递归)

算法:

利用递归深度优先搜索每个节点,每经过一个节点,sum值减去当前节点的值,继续搜索子节点。直到叶子节点的时候判断sum,为0返回true,否则返回false。

代码:

112-路径总和

复杂度分析

  • 时间复杂度:我们访问每个节点一次,时间复杂度为O(N),其中N是节点个数。
  • 空间复杂度:最坏情况下,整棵树是非平衡的,例如每个节点都只有一个孩子,递归会调用N次(树的高度),因此栈的空间开销是O(N) 。但在最好情况下,树是完全平衡的,高度只有 log(N),因此在这种情况下空间复杂度只有O(log(N)) 。

2.2 bfs广搜(迭代)

算法:

我们可以用栈将递归转成迭代的形式,深度优先搜索在除了最坏情况下都比广度优先搜索更快。最坏情况是指满足目标和的 root->leaf 路径是最后被考虑的,这种情况下深度优先搜索和广度优先搜索代价是相通的。

使用迭代的思路是:利用队列,每次保存当前节点以及剩余的sum,如果是叶子节点并且剩余的sum为0则返回true。否则,把节点的左右子节点分别压入队列,更新sum值。

所以我们从包含根节点的栈开始模拟,剩余目标和为 sum - root.val,然后开始迭代。弹出当前元素,如果当前剩余目标和为 0 并且在叶子节点上返回 True;如果剩余和不为零并且还处在非叶子节点上,将当前节点的所有孩子以及对应的剩余和压入栈中。

112-路径总和

复杂度分析:

  • 时间复杂度:和递归方法相同是O(N)。
  • 空间复杂度:当树不平衡的最坏情况下是O(N) 。在最好情况(树是平衡的)下是 O(log(N))。
马谦马谦马谦
  • 本文由 发表于 2018年9月4日18:51:46
  • 转载请务必保留本文链接:https://www.dyxmq.cn/program/algorithms/path-sum.html
匿名

发表评论

匿名网友 填写信息

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