用递归的思想实现二叉树前、中、后序迭代遍历

[woai3c]

先复习一下前、中、后遍历的顺序：

1. 前序遍历顺序：中-左-右
2. 中序遍历顺序：左-中-右
3. 后序遍历顺序：左-右-中

用递归来写二叉树遍历是非常简单的，例如前序遍历的代码如下：

const result = []
function preorderTraversal(node) {
    if (!node) return null
    result.push(node.val)
    preorderTraversal(node.left)
    preorderTraversal(node.right)
}

preorderTraversal(root)

我们都知道，在调用函数时，系统会在栈中为每个函数维护相应的变量（参数、局部变量、返回地址等等）。

例如有 a,b,c 三个函数，先调用 a，a 又调用 b，b 最后调用 c。此时的调用栈如图所示：

为什么要说这个呢？因为递归遍历的执行过程就是这样的，只不过是函数不停的调用自身，直到遇到递归出口（终止条件）。

举个例子，现在要用递归前序遍历以下二叉树：

   1
    \
     2
    /
   3

它的遍历顺序为 1-2-3，调用栈如图所示：

理解了递归调用栈的情况，再来看看怎么利用递归思想实现前序迭代遍历：

function preorderTraversal(root) {
    const result = []
    // 用一个数组 stack 模拟调用栈
    const stack = []
    let node = root
    while (stack.length || node) {
        // 递归遍历节点的左子树，直到空为止
        while (node) {
            result.push(node.val)
            stack.push(node)
            node = node.left
        }
        // 跳出循环时 node 为空，由于前序遍历的特性
        // 当前 node 节点的上一个节点必定是它的父亲节点
        // 前序遍历是中-左-右，现在左子树已经到头了，该遍历父节点的右子树了
        // 所以要弹出父节点，从它的右子树开始新一轮循环
        node = stack.pop()
        node = node.right
    }

    return result
}

再看一个具体的示例，用迭代遍历跑一遍：

            1
          /    \
         2      3
        /  \   /  \
       4    5 6    7

1. 初始节点 node 为 1
2. while 遍历完它的左子节点
3. 当前 stack == [1,2,4]
4. 初始节点已经遍历完它下面的最后一个左子节点了，即节点 4 的左子节点，所以现在要开始遍历 4 的右子节点
5. 弹出节点 4 并从它的右子节点开始新的循环
6. 由于节点 4 的右子节点为空，所以不会进入 while 循环，然后弹出节点 4 的父节点 2
7. 再从节点 2 的右子节点开始循环

看到这是不是已经发现了这个迭代遍历的过程和递归遍历的过程一模一样？

而且用递归的思想来实现迭代遍历，优点在于好理解，以后再遇到这种问题马上就能想起来怎么做了。

中序遍历

中序遍历和前序遍历差不多，区别在于节点出栈时，才将节点的值推入到 result 中。

function inorderTraversal(root) {
    const result = []
    const stack = []
    let node = root
    while (stack.length || node) {
        while (node) {
            stack.push(node)
            node = node.left
        }
        
        node = stack.pop()
        result.push(node.val)
        node = node.right
    }
    
    return result
}

后序遍历

前序遍历过程为中-左-右，逆前序遍历过程就是将遍历左右子树的顺序调换一下，即中-右-左。

然后再看一下后序遍历的过程左-右-中，可以看出逆前序遍历顺序的倒序就是后序遍历的顺序。

利用这一特点写出的后序遍历代码如下：

function postorderTraversal(root) {
    const result = []
    const stack = []
    let node = root
    while (stack.length || node) {
        while (node) {
            result.push(node.val)
            stack.push(node)
            node = node.right // 原来是 node.left，这里换成 node.right
        }

        node = stack.pop()
        node = node.left // 原来是 node.right，这里换成 node.left
    }
    
    return result.reverse() // 逆前序遍历顺序的倒序就是后序遍历的顺序
}

参考资料

他来了，他带着他的三兄弟来了，前中后序遍历统一的算法