112. Sum of paths
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
Tip:
- The number of nodes in the tree is in the range
[0, 5000]
内 -1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000
Sequence traversal
Train of thought
We know that we need to find out if there is a path from the root node to the leaf node where the sum of all children is equal to a certain value
So we have to go through the binary tree to figure out whether the sum of the paths is equal to the target value
Here we use sequential traversal
-
Handle boundary conditions, return false if root is empty
-
Declare a stack and place the root node in it first
-
Walk through the stack, pulling out one node at a time, and determine if there are any children at the moment
- If there are child nodes, add the value of the child node to the value of the current node and push the child node back into the array
- If there is no child node, the current node is the leaf node. If it is equal to the target value targetSum, return true
-
If no true is returned at the end of the traversal, the destination path does not exist and false is returned
var hasPathSum = function (root, targetSum) {
if(! root)return false
var queue = [root]
while (queue.length) {
var item = queue.shift()
if (item.left) {
item.left.val += item.val
queue.push(item.left)
}
if (item.right) {
item.right.val += item.val
queue.push(item.right)
}
if(! item.left && ! item.right && item.val === targetSum) {return true}}return false
};
Copy the code