You are given the root node of the binary tree and an integer targetSum representing the targetSum. Determine if there is a path from the root node to the leaf node in the tree where the values of all nodes add up to the target and targetSum. Return true if it exists; Otherwise, return false.

A leaf node is a node that has no children.

Example 1:

Input: root = [13,4,7,2 5,4,8,11, null, null, null, null, 1], targetSum = 22 output: true interpretation: is equal to the target and the root node to leaf node path as shown in the above.Copy the code

Example 2:

Root = [1,2,3], targetSum = 5 output: false If sum is 4, there is no path from the root node to the leaf node where sum = 5.Copy the code

Example 3:

Input: root = [], targetSum = 0 Output: false Description: Since the tree is empty, there is no root to leaf path.Copy the code

breadth-first

First we can think of using breadth-first search to record the path sum from the root node to the current node to prevent double computation.

So we use two queues that store the nodes to be traversed, and the paths and values from the root node to those nodes.

var sumNumbers = function(root) { if(! Root) return false Create two queues // to store the node let nodeQue = [] // to store the sum from the root node to this node let valQue = [] // Queue the root node first Nodeque.unshift (root) valque.unshift (root.val) while(nodeque.length > 0){temp let root = Nodeque.pop () let temp = valque.pop () // If (! root.left && ! Root.right){return true and exit if(temp === targetSum) return true Nodeque.unshift (root.left) // Save the sum of paths at this time valque.unshift (root.left. Val + Temp)} // If (root.right){// If (root.right){nodeque.unshift (root.right) // Save the sum of paths valque.unshift (root.right.val + }} return false;Copy the code

Depth first

Looking at the function we are asked to complete, we can generalize its function: ask if there is a path from the current node root to the leaf node whose path sum is sum.

Given that the sum of the values from the root node to the current node is val, we can turn the big question into a smaller one: is there a path from the children of the current node to the leaf whose sum is sum-val?

If the current node is a leaf node, then we can directly determine whether sum is equal to val (since the path sum has already been determined, which is the value of the current node, we only need to determine whether the path sum satisfies the condition). If the current node is not a leaf node, we simply recursively ask its children if they meet the criteria.

var hasPathSum = function (root, sum) { if (! root) return false; if (! root.left && ! root.right) return (root.val == sum) return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val) };Copy the code