This is the 16th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021″

Binary Tree Postorder Traversal

Today we are going to do a simple problem, the backward traversal of binary trees.

Backward traversal of a binary tree

The title

Given a binary tree, return its backward traversal. Given the root of a binary tree, return the postorder traversal of its nodes’ values.

Example:

Input: root = [1.null.2.3]
Output: [3.2.1]

Input: root = []
Output: []

Input: root = [1]
Output: [1]
Copy the code

Thinking line

Their thinking

First, we need to clarify the traversal rules of binary trees:

Front-order traversal: traverses the middle nodes first and then the left and right child nodes.

Middle traversal: traverses the left node first, then the middle node, and finally the right node

Sequential traversal: traverses the left and right nodes first and the middle nodes last.

Method 1

The easiest way to do a post-order traversal is recursively

  1. Set the variable res to hold the contents of the traversal results.
  2. Returns if the node is empty
  3. If the node is not empty, the left node recurses, the right node recurses
  4. Put the value of the current node into the RES.

The following code


/ * * *@param {TreeNode} root
 * @return {number[]}* /
var postorderTraversal = function(root) {
    const res = [];
    recursion(root, res);
    return res;
}

function recursion(root, res) {
    if(! root)return;
    recursion(root.left, res);
    recursion(root.right, res);
    res.push(root.val);
}
Copy the code

Method 2

We know that any problem that can be solved recursively can be solved iteratively. How do we solve this problem iteratively?

We know that the implementation of recursion is: each recursive call will push the local variables, parameter values and return address of the function into the call stack, and then when recursive return, the last recursive parameters pop up from the top of the stack, so that is why recursion can return the position of the previous layer.

So we can use the stack to achieve the binary tree before the middle order traversal.

Before that, let’s first implement the iteration method of sequential traversal

/ * * *@param {TreeNode} root
 * @return {number[]}* /
var postorderTraversal = function(root) {
    const res = [];
    const stack = [];
    if(root) stack.push(root);
    while(stack.length) {
        node = stack.pop(); / / in the stack
        res.push(node.val);
      	// Preorder traversal order: center-left-right; push order: center-right-left
      	if(node.right) stack.push(node.right); / / right
        if(node.left) stack.push(node.left);   / / left}}Copy the code

And we know that the backorder traversal is left-right-center, so if we change the order of the front order slightly, can we get the reverse order that we want?

We change the order of the pre-traversal (center-left-right) to (center-right-left), and then we reverse the result that we want for the post-traversal.

Let’s do it. Here’s the code

var postorderTraversal = function(root) {
    const res = [];
    const stack = [];
    if(root) stack.push(root);
    while(stack.length) {
        node = stack.pop(); / / in the stack
        res.push(node.val);
      	// Preorder traversal order: center-left-right; push order: center-right-left
        if(node.left) stack.push(node.left);   / / left
        if(node.right) stack.push(node.right); / / right
    }
  	return res.reverse();
}
Copy the code

So that’s our iterative notation.

So can we get our post-order traversal without reverse? The answer is yes. We’re going to put the nodes we’re visiting on the stack, and we’re going to put the nodes we’re going to process on the stack but we’re going to mark them. To mark a node, a null pointer is placed immediately after the node is placed on the stack. This method can also be called notation.

The code implementation is as follows

var postorderTraversal = function(root) {
		const res = [];
    const stack = [];
    if(root) stack.push(root);
    while(stack.length) {
        const cur = stack.pop(); // Eject the topmost node
        if(! cur) { res.push(stack.pop().val)// cur marks the null pointer, and puts the result in
            continue;
        } else {
            // After traversal order: left - right - middle, push order: middle - right - left
            stack.push(cur);/ /
            stack.push(null);
            cur.right && stack.push(cur.right); / / right
            cur.left && stack.push(cur.left); / / left}}return res;
}
Copy the code

Ok, so that’s the summary of the algorithm, the recursive implementation is relatively easy to understand, the iterative implementation is a little bit more complicated to understand, need to understand.