Topic describes

Given a binary tree and a destination sum, determine whether there is a path from the root node to the leaf node in the tree. The sum of the values of all nodes along the path equals the destination sum.

Note: Leaf nodes are nodes that have no child nodes.

Example: Given the following binary tree with the target and sum = 22,

          5
         / \
        4   8
       /   / \
      11  13  4
     /  \      \
    7    2      1
Copy the code

Returns true because there is a target and path 5->4->11->2 from the root node to the leaf node of 22

Their thinking

Some of the problems with binary trees, the first thing that comes to mind is recursion

So I’m going to call it null, and then I’m going to do the leaf node, and when I get to the leaf node, I’m going to see if the number that’s left is equal to my value, otherwise I’m going to do the left and right subtrees one by one, and I’m going to subtract my value from the sum that I’m going to do next time

/ * * *@param {TreeNode} root
 * @param {number} sum
 * @return {boolean}* /
var hasPathSum = function(root, sum) {
    if(root === null) return false;
    
    // if it is a leaf node, see if it is equal to the remaining sum
    if(root.left === null && root.right === null) {
        return root.val === sum;
    }
    // Each time a node is traversed, subtract its own value and recurse again
    return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
};
Copy the code

Sum of Paths II

# Topic Description

Given a binary tree and a destination sum, find all paths from the root node to the leaf node where the sum of paths equals the given destination sum.

Note: Leaf nodes are nodes that have no child nodes.

Their thinking

Using the idea of recursion + backtracking DFS traverses the entire binary tree to find each target path

We first create an empty array result to store the target paths that meet the criteria, and then define the recursive method getPath to find the paths that meet the criteria on each path

Use a stack to store the node path currently traversed

Starting from the root node depth-first traversal, every node, the node into the stack when traversing to the leaf node, reach the leaf node, and the current path is equal to the sum of a given target, is to find a feasible solution, add it to the result array to leaf node, and the current path is not equal to the sum of the given target, Return result at the end of all traversal.

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {TreeNode} root
 * @param {number} sum
 * @return {number[][]}* /
var pathSum = function(root, sum) {
    // Set a result array to store all qualified paths
    const result = [];
    if(root) {
        getPath(root, sum, [], 0, result)
    }
    function getPath(root, sum, stack, curSum, result) {
        // Set a stack to store the nodes in the current path
        // Depth-first traversal starts at the root and pushes each node to the stack
        stack.push(root.val);
        // Set a sum and curSum to identify the sum of the current paths
        curSum += root.val;
        // When the sum of the current paths equals the given target value, a feasible solution is found and added to the result array
        if(! root.left && ! root.right && sum === curSum) { result.push(stack.slice(0));
        }
        if(root.left)  getPath(root.left, sum, stack, curSum, result) 
        
        if(root.right) getPath(root.right, sum, stack, curSum, result) 
        
        stack.pop()
    }
    return result;
};
Copy the code

Sum of paths III

Given a binary tree, each node contains an integer value.

Find paths and the total number of paths equal to the given value.

The path does not need to start at the root node or end at the leaf node, but the path direction must be downward (only from parent to child).

The number of nodes in the binary tree cannot exceed 1000, and the value of the node is an integer ranging from -1000000 to 1000000.

The instance

root = [10.5, -3.3.2.null.11.3, -2.null.1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1return3. And is equal to the8The paths are:1.  5 -> 3
2.  5 -> 2 -> 1
3.  -3 -> 11
Copy the code

Their thinking

Depth-first traversal + recursion

Take each node as the root node, calculate the sum of the paths and sum them up.

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {TreeNode} root
 * @param {number} sum
 * @return {number}* /
var pathSum = function(root, sum) {
    if(root === null) {
        return 0;
    }
    // Path tree whose root is root = sum = number of paths in the left subtree + number of paths in the right subtree + number of paths starting from root
    return pathSum(root.left, sum) + pathSum(root.right, sum) + dfs(root, sum);
    function dfs(root, sum) {
        if(root === null) {
            return 0;
        }
        sum-=root.val;
        return (sum === 0 ? 1 : 0) + dfs(root.left, sum) + dfs(root.right, sum); }};Copy the code