“This is the 30th day of my participation in the Gwen Challenge in November. See 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

Serrated sequence traversal of binary trees

Serrated sequence traversal for binary trees

Topic describes

Given a binary tree, return a zigzag sequence traversal of its node values. (That is, first from left to right, then from right to left for the next layer traversal, and so on, alternating between layers)

The sample

Example 1

Given a binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
Copy the code

Return the zigzag sequence traversal as follows:

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

The problem solving

Solution 1: breadth-first search

Train of thought

This is essentially a binary tree traversal. Therefore, it is not difficult to think of the idea of breadth-first search, which requires a queue to record the nodes of each layer

Unlike sequence traversal, the results of each layer are printed in a zigzag pattern. So, we can print the even-numbered data from left to right and the odd-numbered data from right to left

This problem is almost the same as the high frequency algorithm interview question (19) – print binary trees in a zigzag order, with diagrams of the whole process

code

func zigzagLevelOrder(root *TreeNode) (ans [][]int) { if root == nil { return } queue := []*TreeNode{root} for level := 0; len(queue) > 0; level++ { vals := []int{} q := queue queue = nil for _, node := range q { vals = append(vals, node.Val) if node.Left ! = nil { queue = append(queue, node.Left) } if node.Right ! If level%2 == 1 {for I, n := 0, len(vals); if level%2 == 1 {for I, n := 0, len(vals);  i < n/2; i++ { vals[i], vals[n-1-i] = vals[n-1-i], vals[i] } } ans = append(ans, vals) } return }Copy the code