preface

Path summation related topics are the application of backtracking and binary tree fusion together. Today, I will mainly feel the use of backtracking in binary tree.

The title

Sum of paths three

// Given a binary tree, each node contains an integer value. // // finds 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. // // Example: // // root = [10,5,-3,3,2,null,11,3,-2,null,1], Sum = 8 10 / / / / / / / / / / / / / 5-3 \ \ / / / / / 3 2 11 \ \ / / 3-1/2 / / / return 3. And is equal to 8 path: / / / / 1. 5 - > 3 / / 2. 5 - > 2 - > 1/3. - 3 - > 11 / /Copy the code

The title and dismantling

In fact, it should be the path sum of three questions together, progressive feeling will be stronger, but there is no time today, let’s first list the third question, tomorrow I will write this series.

How many ways are there? How many combinations are there? How many ways are there? What, most probability is backtracking, such as the classic eight queens, so, first of all, the core algorithm thinking is clear, this problem is a backtracking problem.

To make sure you’re backtracking, you have to prune and recurse, and this problem has both positive and negative nodes, and the sum is the same as the target value, so the prune judgment is just the node that is empty and then you don’t go any further.

So what’s left is the idea of backtracking, even though it’s a binary tree, but don’t get too freaked out, if it’s a one-dimensional array, what do we do with this? There are no more than a few steps

  • 1. Start from the beginning and add backwards until you reach the target value. Record a value and keep going because there may be 1, 2, 3, -1, 1, so keep going when you reach the target value.
  • Go to the end, section by section back, exploring other routes.
  • Back to the end, move forward.
  • 4. Repeat steps 1-3.

The difference between a binary tree and a normal backtracking is that in the second step, there’s still room for exploration, so when you take a step back, you have to go in a different direction.

At this point, I wrote the first version of the code

Code error version

    public void dfs(TreeNode root, int sum, int curr) {
        if (root == null) return;
        int currSum = curr - root.val;
        if (currSum == 0) {
            count++;
        } else {
            dfs(root.left, sum, currSum);
            dfs(root.right, sum, currSum);
        }
        dfs(root.left, sum, sum);
        dfs(root.right, sum, sum);

    }
Copy the code

In fact, the idea seems to be no problem, each layer to get a number, I will subtract, reduced to 0, even at the end, the result ++, but less thinking about two points, one is the above said do not stop, resulting in less results; On the other hand, the state of backtracking was cleared incorrectly and returned to the initial state, resulting in the increase of the final calculation results.

After thinking about it for a while, I found a fundamental problem, I can’t distinguish 1,2,3 from 1,2,3, -1, 1; There is no way to distinguish from which node to start the calculation, how many points are added to this link, how many landscapes have been seen, I do not know, then it will become very difficult to implement, so this time also transformed the idea, need to introduce dynamic planning.

We need to maintain a state to mark the path and result before each node. In plain English, we go to a node. How many summation results are there before each node? For example, 1, 2, 3, 4, 5 at the 3 node position, there are three paths ahead of it: 1+2 = 3; 0 + 2= 2, 0 + 0 = 0; We don’t really care who plus who equals who, all we care about is how many times can the sum be 3, how many times can the sum be 2, so this state just stores all the prefixes and the number of prefixes. With reference to the code of several great gods, the final version of the code is as follows

code

class Solution { private int count = 0; public int pathSum(TreeNode root, int sum) { Map<Integer, Integer> sum2Count = new HashMap<>(); sum2Count.put(0, 1); dfs(root, sum2Count, sum, 0); return count; } public void DFS (TreeNode root, Map<Integer, Integer> sum2Count, int sum, int ssum) {// If (root == null) return; Int currSum = ssum + root.val; Count += sum2count. getOrDefault(currSum -sum, 0); Sum2count. put(currSum, sum2Count.getorDefault (currSum, 0) + 1); DFS (root.left, sum2Count, sum, currSum); DFS (root.right, sum2Count, sum, currSum); Sum2Count. Put (currSum, sum2Count. Get (currSum) -1); }Copy the code

conclusion

To sum up the solution of this problem, the solution of today’s rare problem is not very smooth, after writing, it is not very convenient for other students to understand this problem, more or my own idea of the topic itself, not enough structure and constructive, this need to be optimized.

This article is participating in the “Nuggets 2021 Spring recruiting campaign. Click here to view