The title
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.
Train of thought
DFS prefix and traceback
The prefix sum (in the tree case) is the sum of the paths from the root node to this node
Since the request does not necessarily start at the root, find a two-node path and =target that is the difference between the prefix and the sum of the two nodes =target. So the switch is to find a node with a prefix and :sum=presum-tagert.
Note:
HashMap: to reduce run read time,key is prefix and, value is prefix and =key number of nodes
Backtracking: Since the problem defines the direction downward, only the prefix and difference between nodes on the same path (between a node and one of its ancestors) makes sense. So after the current node is processed, it needs to remove the prefix and from the map before going to the next branch path. Backtracking is doing something (undo/remove selection) after recursion to maintain recursion validity.
// define a global variable to store the number of paths and =target int res = 0; Public int pathSum(TreeNode root, int targetSum) {// Create HasMap to store path and HashMap<Integer,Integer> map = new HashMap<>(); Map.put (0,1); DFS(root,targetSum,map,0); // return DFS(root,targetSum,map,0); return res; } // Compute node prefixes and and into map at the same time, return the value of the prefix and. Public int DFS(TreeNode root, int targetSum,HashMap<Integer,Integer> map,int sum){if(root==null){return 0; } sum += root.val; // Read the prefix and the number of nodes with sum-targetsum from the map using res. res += map.getOrDefault(sum-targetSum,0); Map. put(sum,map.getOrDefault(sum,0)+1); // res += DFS(root.left,targetSum,map,sum); // res += DFS(root.right,targetSum,map,sum); / / DFS traversal around node (root) left, targetSum, map, sum); DFS(root.right,targetSum,map,sum); // Important: Because the path direction is downward, it makes sense to change the prefix and difference between the node and one of its ancestors, so it should be removed after the current node is processed. map.put(sum,map.get(sum)-1); return sum; }}Copy the codeTwo, double recursion
This kind of problem requires a similar calculation starting at each node, so the first recursion is used to traverse the nodes, and the two recursions are used to process the nodes for a depth-first search.
class Solution { int pathnumber; Public int pathSum(TreeNode root, int sum) {if(root == null) return 0; Sum(root,sum); pathSum(root.left,sum); pathSum(root.right,sum); return pathnumber; Public void Sum(TreeNode root, int Sum){if(root == null) return; sum-=root.val; if(sum == 0){ pathnumber++; } Sum(root.left,sum); Sum(root.right,sum); }} `Copy the codeThe time complexity is very high, and the following is also calculated when calculating the SUM. Optimization can take out the left and right subtrees.
int pathnumber; public int pathSum(TreeNode root, int sum) { if(root == null) return 0; Sum(root,sum); } public int path(TreeNode root, int sum){ pathSum(root.left,sum); pathSum(root.right,sum); return pathnumber; } public void Sum(TreeNode root, int sum){ if(root == null) return; sum-=root.val; if(sum == 0){ pathnumber++; } Sum(root.left,sum); Sum(root.right,sum); }}Copy the code