8000 Add PathSum · dnshi/Leetcode@599d6ab · GitHub
[go: up one dir, main page]
Skip to content

Commit 599d6ab

Browse files
dnshidnshi
committed
Add PathSum
1 parent cc2515a commit 599d6ab

File tree

2 files changed

+64
-0
lines changed

2 files changed

+64
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -149,6 +149,7 @@
149149
|121|[Best Time to Buy and Sell Stock](https://leetcode.com/problems/best-time-to-buy-and-sell-stock) | [JavaScript](./algorithms/BestTimeToBuyAndSellStock.js)|Easy|
150150
|119|[Pascal's Triangle II](https://leetcode.com/problems/pascals-triangle-ii) | [JavaScript](./algorithms/PascalsTriangle_II.js)|Easy|
151151
|118|[Pascal's Triangle](https://leetcode.com/problems/pascals-triangle) | [JavaScript](./algorithms/PascalsTriangle.js)|Easy|
152+
|112|[Path Sum](https://leetcode.com/problems/path-sum)|[JavaScript](algorithms/PathSum.js)|Easy|
152153
|111|[Minimum Depth of Binary Tree](https://leetcode.com/problems/minimum-depth-of-binary-tree) | [JavaScript](./algorithms/MinimumDepthOfBinaryTree.js)|Easy|
153154
|108|[Convert Sorted Array to Binary Search Tree](https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree) | [JavaScript](./algorithms/ConvertSortedArrayToBinarySearchTree.js)|Easy|
154155
|107|[Binary Tree Level Order Traversal II](https://leetcode.com/problems/binary-tree-level-order-traversal-ii) | [JavaScript](./algorithms/BinaryTreeLevelOrderTraversal_II.js)|Easy|

‎algorithms/PathSum.js

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
// Source : https://leetcode.com/problems/path-sum
2+
// Author : Dean Shi
3+
// Date : 2021-12-14
4+
5+
/***************************************************************************************
6+
* Given the root of a binary tree and an integer targetSum, return true if the tree
7+
* has a root-to-leaf path such that adding up all the values along the path equals
8+
* targetSum.
9+
*
10+
* A leaf is a node with no children.
11+
*
12+
* Example 1:
13+
*
14+
* Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
15+
* Output: true
16+
* Explanation: The root-to-leaf path with the target sum is shown.
17+
*
18+
* Example 2:
19+
*
20+
* Input: root = [1,2,3], targetSum = 5
21+
* Output: false
22+
* Explanation: There two root-to-leaf paths in the tree:
23+
* (1 --> 2): The sum is 3.
24+
* (1 --> 3): The sum is 4.
25+
* There is no root-to-leaf path with sum = 5.
26+
*
27+
* Example 3:
28+
*
29+
* Input: root = [], targetSum = 0
30+
* Output: false
31+
* Explanation: Since the tree is empty, there are no root-to-leaf paths.
32+
*
33+
* Constraints:
34+
*
35+
* The number of nodes in the tree is in the range [0, 5000].
36+
* -1000 <= Node.val <= 1000
37+
* -1000 <= targetSum <= 1000
38+
*
39+
*
40+
***************************************************************************************/
41+
42+
/**
43+
* Definition for a binary tree node.
44+
* function TreeNode(val) {
45+
* this.val = val;
46+
* this.left = this.right = null;
47+
* }
48+
*/
49+
/**
50+
* @param {TreeNode} root
51+
* @param {number} sum
52+
* @return {boolean}
53+
*/
54+
var hasPathSum = function(root, sum) {
55+
if (!root) {
56+
return false;
57+
}
58+
const targetSum = sum - root.val
59+
if (targetSum === 0 && !root.left && !root.right) {
60+
return true
61+
}
62+
return hasPathSum(root.left, targetSum) || hasPathSum(root.right, targetSum)
63+
};

0 commit comments

Comments
 (0)
0