-
Notifications
You must be signed in to change notification settings - Fork 25
/
0112-path-sum.js
52 lines (42 loc) · 1.26 KB
/
0112-path-sum.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
// 112. Path Sum
// Easy 34%
// 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.
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {number} sum
* @return {boolean}
*/
const hasPathSum = function(root, sum) {
if (root == null) return false
if (root.val === sum && root.left == null && root.right == null) return true
sum -= root.val
return hasPathSum(root.left, sum) || hasPathSum(root.right, sum)
}
const TreeNode = require('../structs/TreeNode')
;[
[[5,4,8,11,null,13,4,7,2,null,null,null,1], 22], // true
].forEach(([array, sum]) => {
console.log(hasPathSum(TreeNode.from(array), sum))
})
// Solution:
// 每当是叶子节点的时候,判断路径和时候为给定值。
// 使用减法减小给定值,来代替路径和,可减少一个参数的传递。
// Submission Result: Accepted