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