“This is the 22nd day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Brush algorithm, is never to memorize the problem, but to practice the actual problem into a concrete data structure or algorithm model, and then use the corresponding data structure or algorithm model to solve the problem. In my opinion, with this kind of thinking, I can not only solve the interview problems, but also learn to think in daily work. How to abstract the actual scene into the corresponding algorithm model, so as to improve the quality and performance of the code

Binary tree neutral path of a certain value (2)

The sum of paths II

Topic describes

Given the root node of the binary tree, root, and an integer target and targetSum, find all paths from the root node to the leaf node where the sum of paths is equal to the given targetSum

A leaf node is a node that has no children

The sample

Example 1

Input: root = [13,4,7,2 5,4,8,11, null, null, null, 5, 1], targetSum = 22 output: [,4,11,2 [5], [5,8,4,5]]Copy the code

Example 2

Input: root = [1,2,3], targetSum = 5 output: []Copy the code

Example 3

Input: root = [1,2], targetSum = 0Copy the code

Tip:

  • The total number of nodes in the tree is in the range[0, 5000] 内
  • 1000 <= Node.val <= 1000
  • 1000 <= targetSum <= 1000

The problem solving

Solution 1: depth-first search

Train of thought

The sum of numbers from the root node to the leaf node is the same as the sum of numbers from the root node to the leaf node. Essentially, we need to traverse every path from the root node to the leaf node. It’s easy to think of depth first

Depth-first search: randomly choose a fork in the road to go, when you find that there is no way to go, go back to the previous fork, choose a new road to continue until you have covered all the circumstances

If you want the sum of the paths from the node to the leaf, if you want the sum of the paths from the children of the root node to the leaf, you do the same thing, so you can recurse. In the traversal process, the value of each node is recorded, and the path sum is accumulated

  • If the left and right child nodes of the node are empty and the path and are the target values, the path is valid
  • If the left and right nodes are not empty, continue traversing

Just look at the code

code

Func pathSum(root *TreeNode, targetSum int) [][]int { var res [][]int eachPath := []int{} var dfsPathSum func(root *TreeNode, last int) dfsPathSum = func(root *TreeNode, last int) { if root == nil { return } last -= root.Val eachPath = append(eachPath, Root.val) defer func() {eachPath = eachPath[:len(eachPath)-1] }() if root.left == nil && root.Right == nil && last == 0 {res = append(res, append([]int(nil), eachPath...) ) return } dfsPathSum(root.Left, last) dfsPathSum(root.Right, last) } dfsPathSum(root, targetSum) return res }Copy the code

Solution two: breadth-first search

Train of thought

We have already encountered many tree problems using depth first search and breadth first search, and also said that depth first search can be solved by breadth first search (and vice versa).

Breadth-first search: a “carpet” layered search strategy that searches first for the nearest vertex to the start, then the next closest, and then out

Depth-first search is a kind of sequential traversal in essence. So the difficulty with breadth-first search in this case is, if you go back to the path, because breadth-first doesn’t go all the way to the bottom, it goes down a layer. So, when we search for the left and right child nodes to be empty, and we have our target value, we should be able to go back to the following node based on the current node, and that will give us the path

Therefore, we need to record the parent node of each node in the search process, which is convenient to push the path later. With that in mind, the code is ready to write

Add nonsense: you may brush a dozen or even two dozen to the tree problem, meet the deformation of the tree problem still can’t do (like me), quite frustrated. Really, don’t panic, brush down, be sure to sum up, when some solution type of questions classified summary, I believe that we can master (I am currently in the classification of brush tree questions, about these two weeks brush about the same, and then began to front tree questions for a detailed summary)

Will not see the answer, knock not out to knock a few more then, no question is knocked once again will always remember. The thought and the thought process is more important than the result

code

Struct {node *TreeNode left int} func pathSum2(root *TreeNode, TargetSum int) (res [][]int) {if root == nil {return [][]int{}} parent := map[*TreeNode]*TreeNode{} // Used to record the parent of each node GetPath := func(node *TreeNode) (path []int) {for; func(node *TreeNode) (path []int) {for; node ! = nil; Node = parent[node] {path = append(path, node.val)} for I, j := 0, len(path)-1; i < j; I ++ {path[I], path[j] = path[j], path[I] j--} return} = []pairs{{root, targetSum}} for len(bfsQueue)! = 0 { pair := bfsQueue[0] bfsQueue = bfsQueue[1:] node := pair.node left := pair.left - node.Val if node.Left == nil && node.Right == nil { if left == 0 { res = append(res, getPath(node)) } } else { if node.Left ! = nil { parent[node.Left] = node bfsQueue = append(bfsQueue, pairs{node.Left, left}) } if node.Right ! = nil { parent[node.Right] = node bfsQueue = append(bfsQueue, pairs{node.Right, left}) } } } return res }Copy the code