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

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

前序遍历（preorderTraversal）

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

中序遍历（inorderTraversal）

第一种方法

复制
1const inorderTraversal = function(root) {
2    const res = [], stack = []
3    while(root || stack.length) {
4        // 中序遍历，首先迭代左孩子，左孩子依次入栈
5        if(root.left) {
6            stack.push(root)
7            root = root.left
8        // 如果左孩子为空了，输出节点，去右孩子中迭代，
9        } else if(root.right) {
10            res.push(root.val)
11            root = root.right
12        // 如果左右孩子都为空了，输出当前节点，栈顶元素出栈，也就是回退到上一层，此时置空节点左孩子，防止while循环重复进入
13        } else if(!root.left && !root.right) {
14            res.push(root.val)
15            root = stack.pop()
16            root && (root.left = null)
17        }
18    }
19    return res
20};

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

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

复制
1 const inorderTraversal = function(root) {
2    const res = [], stack = []
3    let node = root;
4    while (stack.length > 0 || node !== null) {
5        // 这里用当前节点node是否存在，简化代码，
6        if (node) {
7            stack.push(node);
8            node = node.left
9        } else {
10            node = stack.pop();
11            res.push(node.val);
12            node = node.right;
13        }
14    }
15    return res;
16};

后序遍历（postorderTraversal）

第一种方法

复制
1// 1, 先依次遍历左孩子, 在栈中依次记录，当左孩子为空时，遍历到叶子节点 //跳回上一层节点, 为防止while循环重复进入，将上一层左孩子置为空
2// 2, 接着遍历右孩子, 在栈中依次记录值，当右孩子为空时, 遍历到叶子节点
3// 跳回上一层节点, 为防止while循环重复进入，将上一层右孩子置为空
4const postorderTraversal = function(root) {
5    let res = [], stack = []
6    while (root || stack.length) {
7        if (root.left) {
8            stack.push(root)
9            root = root.left
10        } else if (root.right) {
11            stack.push(root)
12            root = root.right
13        } else {
14            res.push(root.val)
15            root = stack.pop()
16            if (root && root.left) root.left = null
17            else if (root && root.right) root.right = null
18        }
19    }
20    return res
21};

第二种方法（逆序思维）

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

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

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

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

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