LeetCode brush problem, binary tree after order traversal (145)

Binary tree back order traversal

Given a binary tree, return a sequential traversal of it. Recursion is easy, can you do it iteratively?

The problem solving code

The essence of recursion is to use the stack to calculate, so we manually create a stack, until the bottom tree node, according to the root of the left and right order to push the stack.

var postorderTraversal = function(root) {
  if(! root)return [];
  let res = [];
  let stack = [root]; // Insert the root node
  while (stack.length) {
    const root = stack.pop(); // Pop up the current root node because it has already been operated.
    res.unshift(root.val); // Since the array is traversed sequentially, the current root node is pushed to the top of the array. If there are subtrees, the root node of the subtree is pushed to the top of the stack.
    if (root.left) { // If there is a left subtree, push the current left subtree onto the stack and continue the traversal
      stack.push(root.left)
    }
    if (root.right) { // If there is a right subtree, push the current right subtree onto the stack and continue the traversal
      stack.push(root.right)
    }
  }
  return res;
};
Copy the code