“This is the 10th 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

Print binary trees in glyph order

LeetCode – Offer 32-III. Prints binary tree III from top to bottom

Topic describes

Implement a function to print a binary tree in glyph order, that is, the first line is printed from left to right, the second line is printed from right to left, the third line is printed from left to right, and so on

Such as:

Given a binary tree:

[3,9,20, NULL, NULL,15,7] 3 / \ 9 20 / \ 15 7Copy the code

Returns the result of its hierarchical traversal:

[[3], [20,9], [15,7]Copy the code

The sample

Example 1

Input: {1,2,3,#,#,4,5} return value: [[1],[3,2],[4,5]] as explained in the topic, the first layer is the root node, print the result from left to right, the second layer is from right to left, and the third layer is from left to right.Copy the code

Example 2

Input: {8,6,10,5,7,9,11} return values: [[8],[10,6],[5,7,9,11]Copy the code

Example 3

Input: {1,2,3,4,5} return value: [[1],[3,2],[4,5]]Copy the code

The problem solving

Solution 1: double – ended queue

Train of thought

When I first thought about this problem, I actually used stack + queue, odd numbered stacks, even numbered stacks, and then when I fetched the nodes, I fetched the right node, then the left node, and I realized that when I got to level 4, I didn’t get it right

And then you think of a two-endian queue, and because of that, it’s easy to think of a two-endian queue, a two-endian queue, and this is easy

The first step is to use two queues

  • Queue: If the nodes in the queue are even-numbered, the elements in the queue are first placed in the result set res, then the elements in the queue are accessed in reverse order, and the children of each element are placed in the temporary queue tmpQueue in the order of first right node and then left node. If it is an odd number of layers, the elements in the queue are first placed in the result set RES in order, and then the elements in the queue are accessed in reverse order, and the children of each element are placed in the temporary queue tmpQueue in the order of first left node and then right node
  • TmpQueue: Used to temporarily store nodes of each tier

The text is abstract. Look at the picture

Level = 0 (even level)

  1. The elements in queue are iterated sequentially and placed in the result set res
  2. Fetch the elements from the queue in reverse order, and place the nodes at the next level into the tmpQueue in the order from the right subtree to the left
  3. Assign tmpQueue to queue

Level = 1 (odd-numbered layer)

  1. The elements in queue are iterated sequentially and placed in the result set res
  2. Fetch the elements from the queue in reverse order, and place the nodes at the next level into the tmpQueue in the order from the left to the right subtree
  3. Assign tmpQueue to queue

Level = 2 (even level)

  1. The elements in queue are iterated sequentially and placed in the result set res
  2. Fetch the elements from the queue in reverse order, and place the nodes at the next level into the tmpQueue in the order from the right subtree to the left
  3. Assign tmpQueue to queue

Level = 3 (odd-numbered layer)

code

var res [][]int if root == nil { return res } queue := []*TreeNode{root} level := 0 for len(queue) ! = 0 { tmpQueue := []*TreeNode{} res = append(res, []int{}) for _, node := range queue { res[level] = append(res[level], node.Val) } if level % 2 == 0 { for i:=len(queue)-1; i >= 0; i-- { if queue[i].Right ! = nil { tmpQueue = append(tmpQueue, queue[i].Right) } if queue[i].Left ! = nil { tmpQueue = append(tmpQueue, queue[i].Left) } } } else { for i:=len(queue)-1; i >= 0; i-- { if queue[i].Left ! = nil { tmpQueue = append(tmpQueue, queue[i].Left) } if queue[i].Right ! = nil { tmpQueue = append(tmpQueue, queue[i].Right) } } } queue = tmpQueue level++ } return resCopy the code