【Golang Theme learning Month 】 Brushing questions is much better than playing games. The sense of achievement is getting stronger and stronger. I insist on brushing one question every day, exercising 30 minutes every day, waiting for 8-block abs and waiting for big factory offer.

😄


  \color{red}{~}

I believe that if you encounter this problem in the interview, logical, correct expression, tear

There should be more than a few candidates.

Leecode 102. Sequence traversal of binary trees

Given a binary tree, return the values of nodes traversed in order. (That is, layer by layer, all nodes are accessed from left to right).

 

Example: binary tree: [3,9,20,null,null,15,7],

Return the sequence traversal result:

[[3], [9,20], [15,7]

Sequential traversal, as the name suggests, is layer by layer, top to bottom, left to right.

At this point, let’s think can we do that with a stack?

Because the stack is fifo, but we’re asking for a sequential traversal, which is obviously fifO

Then you use the queue data structure because it’s first in, first out.

Reference code

Define a tree

Struct {* Val int Left *TreeNode // Left * Right *TreeNode // right node *} */Copy the code

  1. Dequeue the entire tree.

  2. Take out the tree and add the root node to the array.

  3. If the left node of the tree is not empty, it adds to the track queue, and if the right node is not empty, it adds to the track queue.

4. If the queue is not empty, pop the first one in, add the root node to the array, and return to step 3.

  1. Discards the root node into the array.

GO language version of recursion

func levelOrder(root *TreeNode)[] []int {
    ret := [][]int{}  // Define an array to store after traversal
    if root == nil {
        return ret
    }
    q := []*TreeNode{root}  // Select the entire tree into the queue
    for i := 0; len(q) > 0; i++ {
        ret = append(ret, []int{})  
        p := []*TreeNode{}
        for j := 0; j < len(q); j++ {
            node := q[j]
            ret[i] = append(ret[i], node.Val)
            ifnode.Left ! =nil {
                p = append(p, node.Left) // 
            }
            ifnode.Right ! =nil {
                p = append(p, node.Right)
            }
        }
        q = p
    }
    returnRet} sincerely thank you handsome force beautiful girls can see here, if this article is written well, feel something to ask for praise 👍 for attention ❤️ for share 👥 right8It's really useful for me with abs!! If there are any mistakes in this blog, please comment, thank you very much! ❤ ️ ❤ ️ ❤ ️ ❤ ️Copy the code