二叉树前中后序遍历的非递归实现

递归改非递归一般都会用到栈这个结构，栈的特点就是先进后出，所以说栈其实是维护了一个特定顺序的结构。

我们先定义这么一种操作：

左遍历：指从给定节点开始无限遍历其左子节点直到叶子节点为止，并将其依次压入栈中。(这样在栈中的节点就都满足一个性质：入栈时一定是先根后左，出栈时一定是先左后根)

function traversal(node) {
    const stack = []
    while(node) {
        console.log(node) // ------> @1
        stack.push(node)
        node = node.left
    }
    while(stack.length) {
        node = stack.pop()
        console.log(node) // ------> @2
    }
}

如果我们在入栈的时候访问节点(@1)，则可以保证根->左的顺序

如果我们在出栈的时候访问节点(@2)，则可以保证左->根的顺序

这里大家肯定会问，这个只是从根节点开始的左子节点的顺序呀，如果有右子节点怎么办呢？

我们拿先序遍历举例说明：

先序遍历要求的顺序是 根->左->右 。由前面的讨论我们已经可以做到根->左的顺序访问了，即只要做到入栈时访问即可。

那么如果有右子节点该如何处理呢？右子节的入栈条件是什么呢？

要解决这个问题我们需要先定义好出栈的含义，首先我们可以明确的是，对于先序遍历来说，入栈时访问，因此按照我们之前的定义，根节点一定在左子节点前被访问，而出栈的时机则是左遍历结束，因为此时对于栈顶节点来说：

该节点的根节点一定访问过了(入栈时)
该节点没有左子节点(根据左遍历的定义即可推出)，或左子节点已经访问过了

而这不正是访问右子节点的前置条件吗？换句话说，直接对出栈节点的右子节点左遍历。

function traversal(node) {
    const stack = []
    while (stack.length > 0 || node) {
        while(node) {         // -----> @1
            console.log(node) // 访问节点
            stack.push(node)
            node = node.left
        }
        if(stack.length) {
            node = stack.pop() // 此时的栈顶节点的根和左都可以保证已经访问过
            node = node.right // -----> @2
        }
    }
}

@1处的 while 循环是我们定义的 左遍历，而对右节点左遍历就是把当前 node 赋值为右子节点(@2)，并跳到@1处开始右节点的左遍历

按照上述讨论我们再来分析下中序遍历

中序遍历要求的顺序是 左->根->右 。由前面的讨论我们已经可以做到左->根的顺序访问了，即只要做到出栈时访问即可。

我们通过入栈维护了根->左的存储顺序，而又通过出栈获取左->根的访问顺序。

此时出栈的时机也是左遍历结束，因为此时对于栈顶节点来说：

该节点左子节点一定访问过了
现在正好需要访问该节点，并对右子树进行左遍历

function traversal(node) {
    const stack = []
    while (stack.length > 0 || node) {
        while(node) {
            stack.push(node)
            node = node.left
        }
        if(stack.length) {
            node = stack.pop() // 此时的栈顶节点的左子树都已访问过
            console.log(node) // 访问节点
            node = node.right // 准备左遍历右子树
        }
    }
}

大家可能已经注意到，前序遍历和中序遍历的代码几乎一样，只是访问的时机不同。

最后我们再来看下后序遍历

相比于前序和中序，后序稍微复杂点。目前我们已经可以做到根->左或者左->根的访问顺序了，但是后序遍历要求左->右->根，显然我们能够参考的是之前实现的左->根的定义，即出栈时访问。但是后序遍历的右节点是介于左和根之间的，这点则和中序遍历不同，因此对于出栈的处理也不同。我们知道中序遍历中出栈的条件是左遍历结束。但是后序遍历时，判断栈顶节点能否出栈除了左遍历结束还有两种情况需要考虑：

右子树还没有访问，需要先遍历右子树（不可以出栈）；
右子树已经访问过了，可以访问该节点了（可以出栈）。

问题的关键就在于右子树有没有被访问过，因此我们需要定义一个变量保存上一个被访问的节点，以此来区分上述的两种情况。

function traversal(node) {
    const stack = []
    let lastVisit = null
    while (stack.length > 0 || node) {
        while(node) {
            stack.push(node)
            node = node.left
        }
        if(stack.length) {
            node = stack[stack.length - 1] // 查看栈顶节点
            if (!node.right || node.right === lastVisit) { // 栈顶节点没有右子节点或右子节点已经访问过，则可以访问该节点
                node = stack.pop()
                console.log(node) // 访问节点
                lastVisit = node // 更新最新访问节点
                node = null // node 置空跳过while循环，再次处理栈
            } else {
                node = node.right // 栈顶节点的右子树没有遍历，则开始遍历右子树
            }
        }
    }
}

总结一下:

前序遍历：左遍历根节点，入栈时访问，出栈时左遍历右子节点

中序遍历：左遍历根节点，出栈时访问，出栈时左遍历右子节点

后序遍历：左遍历根节点，出栈时访问，记录上次访问的节点，出栈前判断上次访问节点是否为其右子节点，是则允许出栈，否则继续左遍历右子节点