This is the first day of my participation in the First Challenge 2022

The title

Interview question 04.12. Summing up paths

Given a binary tree, each node contains an integer value (either positive or negative). Design an algorithm that prints the number of paths where the sum of node values equals a given value. Note that the path does not have to start or end at the root or leaf of the binary tree, but it does have to go down (only from the parent to the child).

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

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

Returns:

3 explanation: the paths where and are 22 are: [5,4,11,2], [5,8,4,5], [4,11,7]Copy the code

Tip:

  • The number of nodes is less than = 10000

Train of thought

  1. From the top down, enumerate each node as the root node, so that one BFS walk we can enumerate all the possibilities;
  2. When each node is the root node, it can either go left child or right child, and each step is faced with this choice, so we can turn this into a recursive problem;
  3. sumsumAfter we get past the current node we have to subtract the value of the current node, so in the next round we just have to findSum - The value of the current nodeEqual values;
  4. When we find it, do we have to go down to find it? Many friends may fall into a mistaken thinking, think I have found it, why do WE have to go down? They don’t actually tell us that the value of the node is a positive integer, which means that the value could be0Or negative, so if the next node is zero0, plus the current node is still the original value, but it is another path. So this problem we found is not complete, we have to complete the scan from each node down once;
  5. Each time the value of the current node and what we’re looking forsumAt the same time, we match the result +1, and then continue to go to the left and right nodes until the end, and finally return the sum of all matches of each node.

implementation

/** * 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)return 0;

    let reuslt = 0;
    let queue = [ root ];
    // breadth-first search enumerates the possibilities of each node as the starting node
    while (queue.length) {
        queue = queue.reduce((total, cur) = > {
            // How many paths can the current node match as the root node, plus
            reuslt += findNode(cur, sum);

            // Count valid values for the next round
            cur.left && total.push(cur.left);
            cur.right && total.push(cur.right);

            returntotal; } []); }return reuslt;
};

// Find the number of qualified paths under the current node
function findNode(node, sum) {
    if(! node)return 0;

    let count = 0;
    // If the current value is the required sum, the result is +1
    if (node.val === sum) {
        count++;
    }

    // The next value may be 0, so it still counts one more
    // The next value is just the difference between the current sum and the current value
    count += findNode(node.left, sum - node.val);
    count += findNode(node.right, sum - node.val);

    return count;
}
Copy the code

The results of

If you understand it, you can click on it and see you in the next topic. If there is no accident after the article will be in this form, there are good suggestions welcome to comment area.