`Note:`

Backtracking is easy but slower.
Recursion is quicker and it’s intuitive to use `||`

operator.
Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

Example

1 2 Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 Output: true

`Backtracking`

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 var hasPathSum = function (root, targetSum ) { let result = false ; if (!root) return result; backtracking (root, 0 ); return result; function backtracking (node, sum ) { if (!node.left && !node.right ) { sum += node.val ; if (sum === targetSum) result = true ; } if (node.left ) { sum += node.val ; backtracking (node.left , sum) sum -= node.val ; } if (node.right ) { sum += node.val ; backtracking (node.right , sum); sum -= node.val ; } } };

`Recursion`

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 var hasPathSum = function (root, targetSum ) { return recursion (root, 0 ); function recursion (node, sum ) { if (!node) return false ; if (!node.left && !node.right && sum + node.val === targetSum) return true ; return recursion (node.left , sum + node.val ) || recursion (node.right , sum + node.val ); } };