非递归遍历二叉树

问题

如何用非递归方式实现二叉树的前序、中序、后序遍历？

解答

二叉树递归遍历很简单，但非递归实现需要借助栈来模拟递归过程。假设每个节点有 left、right 指针和 val 属性。

前序遍历

前序遍历顺序：根节点 -> 左子树 -> 右子树

const preorderTraversal = function(root) {
    const stack = [], res = []
    root && stack.push(root)
    
    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
}

中序遍历

中序遍历顺序：左子树 -> 根节点 -> 右子树

方法一：条件判断

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
        // 左右孩子都为空，输出当前节点，回退到上一层
        } else {
            res.push(root.val)
            root = stack.pop()
            root && (root.left = null) // 防止重复进入
        }
    }
    return res
}

方法二：简化版本

const inorderTraversal = function(root) {
    const res = [], stack = []
    let node = root
    
    while(stack.length > 0 || node !== null) {
        if(node) {
            stack.push(node)
            node = node.left
        } else {
            node = stack.pop()
            res.push(node.val)
            node = node.right
        }
    }
    return res
}

后序遍历

后序遍历顺序：左子树 -> 右子树 -> 根节点

方法一：逆序思维（推荐）

后序遍历是前序遍历的逆序过程，使用 unshift 在数组头部插入元素。

const postorderTraversal = function(root) {
    const res = [], stack = []
    root && stack.push(root)
    
    while(stack.length > 0) {
        let cur = stack.pop()
        res.unshift(cur.val) // 头部插入，实现逆序
        cur.left && stack.push(cur.left)
        cur.right && stack.push(cur.right)
    }
    return res
}

方法二：使用 reverse

const postorderTraversal = function(root) {
    const res = [], stack = []
    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() // 最后反转数组
}

关键点

• 使用栈来模拟递归调用过程
• 前序遍历：先入栈右孩子，再入栈左孩子（栈的后进先出特性）
• 中序遍历：先遍历到最左节点，再输出，最后遍历右子树
• 后序遍历：可以看作前序遍历的逆序（根右左 -> 左右根）
• 注意栈为空和当前节点为空的判断条件