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

preface

Today’s topic is simple, two days ago we did the problem of pre-order traversal, the data given by this problem is exactly the same as it, but need is post-order traversal, so it is necessary to understand the basic knowledge of post-order traversal.

A daily topic

N tree traversal. N tree traversal

  • Given the root node of an n-tree, root, returns a back-order traversal of its node values.

  • The n-fork tree is serialized in the input as a sequential traversal, with each set of child nodes separated by null values (see example).

 

Example 1:

Enter: root = [1.null.3.2.4.null.5.6] output: [5.6.3.2.4.1]
Copy the code

Example 2:

Enter: root = [1.null.2.3.4.5.null.null.6.7.null.8.null.9.10.null.null.11.null.12.null.13.null.null.14] output: [2.6.14.11.7.3.12.8.4.13.9.10.5.1]
Copy the code

 

Tip:

  • The total number of nodes is in the range [0, 104]
  • 0 <= Node.val <= 104
  • The height of an n-tree is less than or equal to 1000

Answer key

After the sequence traversal

We just did a pre-order traversal a couple of days ago, so again, we need to understand what post-order traversal is.

Post-order traversal (LRD) is a kind of binary tree traversal, also known as post-root traversal, post-order tour, can be remembered as left and right roots. There are two kinds of post-order traversal: recursive algorithm and non-recursive algorithm.

In binary trees, first left, then right, then root, that is, the left subtree is traversed, then the right subtree is traversed, and finally the root is visited.

Let’s take an actual tree and see what a post-order traversal is:

If we had a tree that looked like this, we would go to the left subtree and then to the right subtree, and then to the root. The sequence traversal of the tree above would be [4,5,2,3,6,1].

Let’s go to traverse the deepest left child, which is 4, then find it right child, which is 5, the last is the root node 2, and 1 and 2 left children, so the next node is 2, then traverse Left child of the root node 1, and then going to traverse the right of his children, namely 3 this subtree, All we have left to do is do the same thing with the 2 subtree, and then we get to the root node 1, and we get the backward traversal up here.

Recursive problem solving

So according to the array given to us above, its order is the root node, left child, right child, then we can recurse to the current deepest left child or right child according to the array, and then recurse outward to get its node value, the order obtained is the post-order traversal we need.

/** * // Definition for a Node. * function Node(val,children) { * this.val = val; * this.children = children; *}; * /

/ * * *@param {Node|null} root
 * @return {number[]}* /
 var postorder = function(root) {
    const ans = new Array()
    dfs = function(node) {
        if(node ! =null) {
            for(const child of node.children)
                dfs(child)
            ans.push(node.val)
        }
    }
    dfs(root)
    return ans
}
Copy the code