LeetCode112. Sum of paths

Topic describes

Public number: hand touch hand front step

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. The sum of all nodes in the path equals the target and targetSum.

A leaf node is a node that has no children.

Enter: root = [5.4.8.11.null.13.4.7.2.null.null.null.1], targetSum = 22Output:true
Copy the code

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {TreeNode} root
 * @param {number} targetSum
 * @return {boolean}* /
/** Solution steps: 1, depth first traversal binary tree, at the leaf node, judge whether the node value of the current path is equal to the target value, if yes, return true 2, traversal end, if no match, return false */
var hasPathSum = function(root, targetSum) {
  if(! root)return false
  let res = false
  const dfs = (n, sum) = > {
    if(! n.left && ! n.right && sum === targetSum) { res =true
    }
    if(n.left) dfs(n.left, sum + n.left.val)
    if(n.right) dfs(n.right, sum + n.right.val)
  }
  dfs(root, root.val)
  return res
};

// The title is reprinted from licou official website:
// https://leetcode-cn.com/problems/path-sum/
Copy the code