Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

【 brush topic diary 】589. N fork tree before traversal

This brush topic diary of the fourth chapter, force deduction for: 589. N fork tree before traversal, simple

I. Title Description:

At first glance, it looks like it’s a little bit harder than the binary trees we’ve done before, right? In fact, it’s not. The solution is always the same, so let’s take a look

Ii. Analysis of Ideas:

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

We learned in college, how do you know if a binary tree is pre-ordered, middle-ordered, or post-ordered?

In simple terms, where is the root, what is the order, for example:

So the front order is, around the root, traverses the root of the tree, traverses the left subtree, and traverses the right subtree

The middle order is left root right, traverses the left subtree of the tree, traverses the root, and traverses the right subtree

The order is left and right roots, traversing the left subtree of the tree, traversing the right subtree, and traversing the root

We know from the problem that this is a multi-fork tree, but the idea is the same as a binary tree, so let’s see

To deduce:

Take example 1 of the case

Input: root = [1, null, 3 4-trichlorobenzene, null, 5, 6] output:,3,5,6,2,4 [1]Copy the code

From the reasoning in the figure, we know that foreorder traversal, we can traverse a binary tree or a multi-tree in the order of traversal left and right to the root, the same idea

The roots are iterated, and the first son from the left is iterated

Then, the first son from the left as the root should also follow the guiding principle of the thought around the root, first traverse the root, and then traverse the first son from the left until the tree has been traversed

2. Try coding

func preorder(root *Node)(ans []int) {
     // Define a function for recursion
      var dfs func(*Node)
        dfs = func(node *Node) {
        // If the current node is empty, it returns directly
        if node == nil {
            return
        }
        // The current node is the root node, first add the result set, then traverse the subtree of the root node
        ans = append(ans, node.Val)
        for _, ch := range node.Children {
            dfs(ch)
        }
    }
    dfs(root)
    return
}
Copy the code

Iv. Summary:

It is relatively simple to use recursion to do the problem of binary tree or multi-fork tree. For binary tree or multi-fork tree, we can use recursion to traverse, or we can use iteration to deal with it. When we encounter iteration, we can share a wave again

Use the above recursive way to achieve binary tree/multi-tree preorder traversal

The time complexity is O(m), and this M is the number of nodes in the multi-fork tree

The space complexity isO(m)

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 ~