二叉树使用递归实现前中后序遍历是非常容易的，本文给出非递归实现前中后序遍历的方法，核心的思想是使用一个栈，通过迭代来模拟递归的实现过程。

下面实现中root代表二叉树根节点，每个节点都具有left,right两个指针，分别指向当前节点左右子树，一个val属性代表当前节点的值

前序遍历（preorderTraversal）

const preorderTraversal = function (root) {
  const stack = [],
    res = [];
  root && stack.push(root);
  // 使用一个栈stack，每次首先输出栈顶元素，也就是当前二叉树根节点，之后依次输出二叉树的左孩子和右孩子
  while (stack.length > 0) {
    let cur = stack.pop();
    res.push(cur.val);
    // 先入栈的元素后输出，所以先入栈当前节点右孩子，再入栈左孩子
    cur.right && stack.push(cur.right);
    cur.left && stack.push(cur.left);
  }
  return res;
};

中序遍历（inorderTraversal）

第一种方法

const inorderTraversal = function (root) {
  const res = [],
    stack = [];
  while (root || stack.length) {
    // 中序遍历，首先迭代左孩子，左孩子依次入栈
    if (root.left) {
      stack.push(root);
      root = root.left;
      // 如果左孩子为空了，输出节点，去右孩子中迭代，
    } else if (root.right) {
      res.push(root.val);
      root = root.right;
      // 如果左右孩子都为空了，输出当前节点，栈顶元素出栈，也就是回退到上一层，此时置空节点左孩子，防止while循环重复进入
    } else if (!root.left && !root.right) {
      res.push(root.val);
      root = stack.pop();
      root && (root.left = null);
    }
  }
  return res;
};

第二种方法（第一种优化）

我们在上一种方法里，条件判断root.left,root.right,其实我们可以只考虑当前节点node，这样我们只需要判断node是否存在，简化代码

const inorderTraversal = function (root) {
  const res = [],
    stack = [];
  let node = root;
  while (stack.length > 0 || node !== null) {
    // 这里用当前节点node是否存在，简化代码，
    if (node) {
      stack.push(node);
      node = node.left;
    } else {
      node = stack.pop();
      res.push(node.val);
      node = node.right;
    }
  }
  return res;
};

后序遍历（postorderTraversal）

第一种方法

// 1, 先依次遍历左孩子, 在栈中依次记录，当左孩子为空时，遍历到叶子节点 //跳回上一层节点, 为防止while循环重复进入，将上一层左孩子置为空
// 2, 接着遍历右孩子, 在栈中依次记录值，当右孩子为空时, 遍历到叶子节点
// 跳回上一层节点, 为防止while循环重复进入，将上一层右孩子置为空
const postorderTraversal = function (root) {
  let res = [],
    stack = [];
  while (root || stack.length) {
    if (root.left) {
      stack.push(root);
      root = root.left;
    } else if (root.right) {
      stack.push(root);
      root = root.right;
    } else {
      res.push(root.val);
      root = stack.pop();
      if (root && root.left) root.left = null;
      else if (root && root.right) root.right = null;
    }
  }
  return res;
};

第二种方法（逆序思维）

再回头看看前序遍历的代码，实际上后序遍历和前序遍历是一个逆序过程

// 结果数组中依次进入的是节点的左孩子，右孩子，节点本身，注意使用的是
// unshift，与前序遍历push不同，每次数组头部添加元素，实际上就是前序 遍历的逆序过程
const postorderTraversal = function (root) {
  const res = [],
    stack = [];
  while (root || stack.length) {
    res.unshift(root.val);
    root.left && stack.push(root.left);
    root.right && stack.push(root.right);
    root = stack.pop();
  }
  return res;
};

第三种方法（逆序思维的另一种写法）

// 和前序遍历区别在于，结果数组res中入栈顺序是当前节点，右孩子，左孩子，最后
// 使用js数组reverse方法反转（逆序），使得输出顺序变为左孩子，右孩子，当前节点，实现后序遍历
const postorderTraversal = function (root) {
  let stack = [],
    res = [];
  root && stack.push(root);
  while (stack.length > 0) {
    let cur = stack.pop();
    res.push(cur.val);
    cur.left && stack.push(cur.left);
    cur.right && stack.push(cur.right);
  }
  return res.reverse();
};

本文详细介绍了二叉树前中后序遍历的非递归实现，核心是借助一个栈stack,使用迭代的方式模拟递归过程