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

[B] [C] [D]

Given a binary tree, return its backward traversal.

Example:

Input: [1, NULL,2,3] 1\2/3 Output: [3,2,1]Copy the code

Advanced: The recursive algorithm is simple, can you do it with an iterative algorithm?

Answer key 1

So first of all, we’re going to do it recursively, the very simple way that this problem says

The solution is as follows:

  1. Recursion terminates when the root is empty
  2. Recursively, the left subtree, the right subtree, and finally the value of the current nodepushTo the result array

The code is as follows:

var postorderTraversal = function(root) {
  const res = [];
  function postorder(root){
    if(root === null) return;
    postorder(root.left);
    postorder(root.right);
    res.push(root.val);
  }
  postorder(root);
  return res;
};
Copy the code

Answer key 2

So how do we do the post-order traversal of a binary tree through an iterative algorithm?

The solution is as follows:

  1. We first initialize a stack and a result array
  2. When a right subtree is present, go all the way down to the right subtree, pushing each node onto the stack and inserting its values in reverse order into the result array
  3. When the right-most subtree is found, pull the pushed element out and point root to its left subtree
  4. If the left subtree exists, the value of the left subtree is inserted into the head of the result array
  5. Such triplet after triplet processing, up to the root, will enter the left subtree processing
  6. In this process, node values are inserted in the order of root right to root left
  7. Because the node values are inserted into the head of the result array each time, the order of the result array values is root left and root right
  8. Return the result array

The code is as follows:

Var postorderTraversal = function(root) {const stack =[], res =[]; While (root | | stack. Length) {/ / all the way down to find the right subtree while (root) {/ / press each node into the stack stack. Push (root); // Insert the values of each node in reverse order into the result array res.unshift(root.val); root = root.right; } // If the left subtree exists, the value of the left subtree will be inserted into the head of the result array root = stack.pop().left; } // The value of the node is inserted in the order of the root to the left. // The value of the node is inserted in the order of the root to the left. };Copy the code

At this point we have completed the post-order traversal of leetcode-145-binary tree

If you have any questions or suggestions, please leave a comment!