112. Path Sum
June 24, 2025
04:32 AM
No headings found
Loading content...
No headings found
Problem
Bài toán yêu cầu kiểm tra xem trong một binary tree có tồn tại một đường đi từ root → leaf nào mà tổng các giá trị các node trên đường đi đó bằng target hay không
Approach
targetSum targetSum - node.val === 0 thì return true false Time and space complexity
Solution
1/**
2 * Definition for a binary tree node.
3 * class TreeNode {
4 * val: number
5 * left: TreeNode | null
6 * right: TreeNode | null
7 * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
8 * this.val = (val===undefined ? 0 : val)
9 * this.left = (left===undefined ? null : left)
10 * this.right = (right===undefined ? null : right)
11 * }
12 * }
13 */
14
15function hasPathSum(root: TreeNode | null, targetSum: number): boolean {
16 if (!root) return false
17 if (!root.left && !root.right) return root.val === targetSum
18 return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val)
19};