Path Sum#

Given a binary tree and a target sum, determine if there is a root-to-leaf path in this tree where the sum of all the node values along the path equals the target sum.

Note: A leaf is a node with no children.

Example#

Given the following binary tree and the target sum sum = 22, return true, because there exists a root-to-leaf path with a sum of 22: 5->4->11->2.

Solution#

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {boolean}
 */
var hasPathSum = function(root, sum) {
    return dfs(root, sum, 0); 
};

function dfs(root, sum, tmp){
    if(!root) return false;
    tmp = tmp + root.val;
    if(!root.left && !root.right) return tmp === sum ;
    return dfs(root.left, sum, tmp) || dfs(root.right, sum, tmp);
}

Idea#

Simply use depth-first search. First, handle the boundary conditions. If the node is null, return false directly. Then add the tmp value to the node value. If this node is a leaf, return whether tmp is equal to sum. Finally, recursively traverse the tree in depth. By using short-circuit evaluation, if the left subtree is true, the right subtree will not be recursively computed, and if the right subtree is true, the upper-level recursive computation will be directly returned. This can achieve the computation of path sum.

Daily Question#

Source#