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 】590. N tree after the order traversal

【 brush topic diary 】590. N after the order of the tree traversal, simple

I. Title Description:

At the first sight of this topic, there is no feeling very familiar, as if in the last article to do

XDM, you are right, this is exactly the same as the previous problem, except that the previous multi-tree traversal is replaced by the multi-tree after traversal

For the last passage, friends who understand, believe that do this after the traversal of the problem (【 brush topic diary 】589. N fork tree before traversalBelieve it or not

Ii. Analysis of Ideas:

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

What is pre-ordered traversal, middle-ordered traversal, and post-ordered traversal of a binary/multi-ordered tree? Post-ordered traversal of a binary tree is traversal of the left subtree, then traversal of the right subtree, and finally traversal of the root

In the case of a multi-fork tree, you traverse the child node of the multi-fork tree, and then the root node

So for today’s postorder traversal of multi-fork trees, we can also use an example to deduce, walk through it together, this kind of recursive traversal of trees, is very much the same

We’re still going to use the example in the problem as an analogy,

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

I’m sure the illustration above will show you how each node is added to the result set. You can also quickly and easily do the post-order traversal of a multi-fork tree, recursive traversal of the left and right roots

2. Try coding

According to the above deduction and analysis, we only need one subtree and one subtree to traverse in the way of left and right roots

func postorder(root *Node) (ans []int) {
    var dfs func(*Node)
    dfs = func(node *Node) {
        if node == nil {
            return
        }
        // Iterate over the child node first
        for _, ch := range node.Children {
            dfs(ch)
        }
        // Add the root node to the result set
        ans = append(ans, node.Val)
    }
    dfs(root)
    return
}
Copy the code

Looking at the above code, do you find that the pre-order traversal is part of the code order adjustment? In fact, it is true that if there is no clear place, you can deduce a few times to understand

Iv. Summary:

The above approach is basically the same as the previous approach of multi-fork tree traversal. So, it is the same for time complexity and space complexity

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 after 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 ~