Make writing a habit together! This is the 7th day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

【 brush topic diary 】429. N tree sequence traversal

This brush topic diary 27, force deduction is: 429. N fork tree sequence traversal, medium

I. Title Description:

Today’s daily question is about trees. Generally speaking, if it is about binary trees, it is relatively easy to understand and do. Although it looks like a medium question, in fact, the implementation method is relatively clear and easy to understand

Let’s take a look

2. What ideas does this question examine? What’s your thinking?

Let’s take a closer look at the important information given by today’s question:

• The tree given in the question is a multi-fork tree. Unlike a binary tree, a node can have at most two child nodes, one left child and one right child, but a multi-fork tree can have multiple child nodes
• We need to traverse the tree sequence, see the name of the meaning, is a layer of traversal

We’ve done binary tree problems before, like traversing the tree in front, back, and middle order, and remember we used recursive, DFS depth-first algorithm

So this time the sequence traversal, is not depth first algorithm?

We can deduce:

Root = [1,null,3,2,4,null,5,6]

The main thing is that we need to understand the following diagram

So let’s go through the tree, layer by layer, layer by layer, layer by layer

When traversing the second layer, we know that the second layer is the child node of the first layer, so when traversing the first layer, we can use a help space to store the addresses of all the child nodes of the first layer, which can be used when traversing the second layer

When traversing the third layer, do the same as when traversing the second layer

So when the traversal of the third layer is completed, we find that none of the nodes of the third layer has children. Therefore, we consider the traversal to be completed

So finally, we can output the node number of each layer

The rest is the process of translating the above ideas, thinking clearly, writing code that is soSO drops

Three, coding

Based on the above logic and analysis, we can translate it into the following code

The encoding is as follows:

/** * Definition for a Node. * type Node struct { * Val int * Children []*Node * } */

func levelOrder(root *Node)(res  [][]int) {
    // If the passed root node is empty, there is no sequence traversal
    if root == nil{
        return
    }
    // Define a queue and place the root node at the head of the queue
    que := []*Node{root}

    forque ! =nil {
        tmp := que
        que = nil
        // Define a slice to store the node data of this layer
        tmpLevel := []int{}

        for _,val := range tmp {
            // Store layer node data
            tmpLevel = append(tmpLevel, val.Val)
            // Queue the children of the current node
            que = append(que, val.Children...)
        }
        // Add the layer node to the result set
        res = append(res, tmpLevel)
    }
    
    return
}
Copy the code

You can see that the structure of the node looks like this

Each node has its own value field and pointer field, which stores a slice containing the addresses of its multiple child nodes

Then, through the above coding, we know that each node of the tree is put into the queue layer by layer, first-in, first-out. After traversing layer by layer, we can get the data results of each layer

This is the breadth-first algorithm, BFS

I believe that through viewing the remarks of the above code, should be to see clearly

Iv. Summary:

You can actually see the time complexity here, which is the number of nodes in the tree, which is O(n), and when we iterate, which is the length of the queue, which is the total number of nodes, so the space complexity is also O(n).

N traversal of a fork tree

Today is here, learning, if there is a deviation, please correct

Welcome to like, follow and favorites

Friends, your support and encouragement, I insist on sharing, improve the quality of the power

All right, that’s it for this time

Technology is open, our mentality, should be more open. Embrace change, live in the sun, and strive to move forward.

I am Nezha, welcome to like, see you next time ~