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

[B] [C] [D]

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

Their thinking

In the binary tree, we need to find the number of nodes and paths equal to the target value. The path here can start at any node and end at any node, but the path must go from top to bottom. So we can start from any node, look down the path, and record the node and value, when the sum value is equal to the target value, it means that we have found a path that meets the conditions, the number of records. The recursive function exits when we find an empty node.

When we’ve done that, we’ve found all the paths that we can take, and we’ve got the number of paths that we can take.

Code implementation

Var pathSum = function(root, sum) {function getPath(node,target){var pathSum = function(root, sum) {function getPath(node,target){ If (node===null) return 0; NodeVal = node.val; // If nodeVal = node.val; // If nodeVal = node.val; If (nodeVal === target) num++ const val = target-nodeVal num+ = getPath(node.left,val) // Num += getPath(node.right,val) // If the left subtree is not empty and the left subtree has not been searched as the starting point // Find the path from the left subtree if(node.left&&! Node.left. Tag){// Label the left subtree as the starting point of node.left. Tag = true; Num += getPath(node.left,sum)} // If (node.right&&! Node.right.tag){// Mark the right subtree to prove that node.right.tag is used as the starting point; Num += getPath(node.right,sum)} return num; Return getPath(root,sum)};Copy the code

It is important to note that in the recursive process, some nodes will be passed many times, so it is necessary to record whether the current node is searched as the starting point to prevent repeated searches.

This completes leetcode- Interview question 04.12- Summation path

If you have any questions or suggestions, please leave a comment! 👏 🏻 👏 🏻 👏 🏻