“This is the 29th day of my participation in the Gwen Challenge in November. See details of the event: 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 search trees and bidirectional linked lists

All paths to a binary tree

Topic describes

You are given the root node of a binary tree, root, and are given all paths from root to leaf, in any order.

A leaf node is a node that has no children

Example 1:

["1->2->5","1->3"]Copy the code

Example 2:

Input: root = [1]Copy the code

Tip:

  • The number of nodes in the tree is in the range[1, 100] 内
  • 100 <= Node.val <= 100

The problem solving

Solution 1: depth-first search

Train of thought

If you read the previous question, it’s the same as the previous question

Binary tree neutral path of a certain value (I)

Binary tree neutral path of a certain value (2)

The maximum path sum in a binary tree

If you know how to get all the paths, you can filter out the paths that do not meet the conditions

It’s a simple case, but it’s actually traversal, and the key is how to traverse. We know that in order to get all the paths, we need to know when I’ve already traversed one path? It must be traversing the leaves. Therefore, we can divide the traversal process into non-leaf nodes and leaf nodes

  • If the current node is not a leaf node, the node is added at the end of the current path and each child node of the node continues to be recursively traversed
  • If the current node is a leaf node, adding the node at the end of the current path gives us a path from the root node to the leaf node, adding the path to the result path array

This is a typical pre-order traversal, which is also the idea of depth-first search

code

Var treePath []string func binaryTreePaths(root *TreeNode) []string{treePath = []string{} dfsEachPath(root, "") return treePath } func dfsEachPath(root *TreeNode, path string) { if root ! = nil { eachPath := path eachPath += strconv.Itoa(root.Val) if root.Left == nil && root.Right == nil { treePath = append(treePath, eachPath) } else { eachPath += "->" dfsEachPath(root.Left, eachPath) dfsEachPath(root.Right, eachPath) } } }Copy the code

Solution two: breadth-first search

Train of thought

We’ve done a lot of binary tree problems, many of which are solved by depth and breadth first search, and basically anything that can be solved by depth first search, you can try breadth first search

Breadth-first search first, we know that we need to use queues. In this case, we need to maintain two queues, which are used to record the nodes of each layer and the path from the root node to the current node

If the current node traversed is a leaf node, the current path can be placed in the result set. If it is a non-leaf node, its children are put into the node queue

code

Func binaryTreePaths2(root *TreeNode) []string{paths := []string{} if root == nil {return paths} nodeQueue := []*TreeNode{root} pathQueue := []string{strconv.Itoa(root.Val)} for i :=0; i < len(nodeQueue); i++ { node, path := nodeQueue[i], pathQueue[i] if node.Left == nil && node.Right == nil { paths = append(paths, path) continue } if node.Left ! = nil { nodeQueue = append(nodeQueue, node.Left) pathQueue = append(pathQueue, path+"->"+strconv.Itoa(node.Left.Val)) } if node.Right ! = nil { nodeQueue = append(nodeQueue, node.Right) pathQueue = append(pathQueue, path+"->"+strconv.Itoa(node.Right.Val)) } } return paths }Copy the code