“This is the 8th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

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

Brute force solution + recursion

We need the sum of all the nodes in the array from top to bottom to be equal to sum

In order to reduce the number of computations, we will directly pass in the result of the last calculation. Next, we only need to continue home on the basis of pre, and pass in an array preArr to keep the value of the node currently being calculated

  • Total is less than sum, in which case we just keep recursing and adding the value of the next node
  • Total is greater than or equal to sum
    • Is equal to sum, res++
    • When the sum is greater than sum, I want to subtract the preceding node so that I don’t need to recurse again and no node is computed ab initio, so I take the preceding node from preArr, total = total-prearr [0], preArr = prearr.slice (1).

Failure: Aborted because the value of the node may be negative

Ideas of violence:

So at the moment, each node is evaluated as the first node

  • Declare res with an initial value of 0
  • Declare a new function, dealRoot, to deal recursively with each node
  • Declare the computedTotal function to compute the value total from root to the current node
    • If total equals sum then res++
    • If not, the recursive call computedTotal continues, passing in the current calculated total value for ease of calculation

After all nodes are processed, return the value of res

var pathSum = function (root, sum) {
    var res = 0
    function dealRoot(root, sum) {
        if (root === null) return 0
        function computedTotal(root, sum, pre) {
            if (root === null) return
            var total = root.val + pre;
            if (total === sum) {
                res++
            }
            computedTotal(root.left, sum, total)
            computedTotal(root.right, sum, total)
        }
        computedTotal(root, sum, 0)
        dealRoot(root.left, sum, 0)
        dealRoot(root.right, sum, 0)
    }
    dealRoot(root, sum)

    return res
};
Copy the code