31、二叉树的先中后序遍历（非递归）

先序遍历

中左右

const preorder = root => {
    if (!root) return
    const stack = [root]
    while (stack.length) {
        const n = stack.pop()
        console.log(n.val);
        if (n.right) stack.push(n.right) // 注意栈先进后出
        if (n.left) stack.push(n.left)
    }
}
preorder(binaryTree)

中序遍历

左中右

const inorder2 = root => {
    if (!root) return
    const stack = []
    let p = root
    while (stack.length || p) {
        while (p) {
            stack.push(p)
            p = p.left
        }
        const n = stack.pop()
        console.log(n.val);
        p = n.right
    }
}
inorder2(binaryTree)

后序遍历

const postorder2 = root => {
    if (!root) return
    const outpuStack = []
    const stack = [root]
    while (stack.length) {
        const n = stack.pop()
        outpuStack.push(n)
        if (n.left) stack.push(n.left)
        if (n.right) stack.push(n.right)
    }
    while (outpuStack.length) {
        const n = outpuStack.pop()
        console.log(n.val);
    }
}
postorder2(binaryTree)