day144-LeetCode 112. Path Sum

题目

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
For example: Given the below binary tree and sum = 22,

      5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

分析

leetcode 104的变形。用递归来计算每条路径的总和。
求根节点到子树的每条可能路径的和,并检测是否和给出的随机数相等。

从父节点出发,如果父节点加左节点不等于给出的随机数,则回退父节点加右节点,
如果不相等且子节点有左右子树则递归上述过程。
直到找到和随机数相等的值返回true,否则返回false

题解

function hasPathEqualSum (root, sum) {
if (root === null) return
let list = []
// 计算总和
sumR2L(root, 0)
return sumR2L(root, 0)
function sumR2L(root, s) {
if (root.left === null && root.right === null) {
// 到底的时候,判断总和是否是与sum相同
list.push(s)
s += root.val
return s === sum
}
// 右边到底
if (root.left !== null && root.right === null) {
return sumR2L(root.left, s + root.val)
}
// 左边到底
if (root.left === null && root.right !== null) {
return sumR2L(root.right, s + root.val)
}
// 两边的树没有到底
return sumR2L(root.left, s + root.val) || sumR2L(root.right, s + root.val)
}
}
文章作者: lmislm
文章链接: http://lmislm.com/2019/06/06/2019-06-06/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 LMISLMのBlog