乐趣区

关于算法:用递归的思想实现二叉树前中后序迭代遍历

jiezi

先温习一下前、中、后遍历的程序：

  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() // 逆前序遍历程序的倒序就是后序遍历的程序}

参考资料

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

退出移动版