二叉树的遍历

前序遍历

递归算法

function preorderTraversal(root) {
    const arr = []

    function preorder(root) {
        if (!root) return
        arr.push(root.val)
        preorder(root.left)
        preorder(root.right)
    }

    preorder(root)

    return arr
}

非递归算法

function preorderTraversal(root) {
    const arr = []
    const stack = []
    let p = root

    while (p || stack.length !== 0) {
        if (p) {
            arr.push(p.val)
            stack.push(p)
            p = p.left
        } else {
            const q = stack.pop()
            p = q.right
        }
    }

    return arr
}

中序遍历

递归算法

function inorderTraversal(root) {
    const arr = []

    function inorder(root) {
        if (!root) return
        inorder(root.left)
        arr.push(root.val)
        inorder(root.right)
    }

    inorder(root)

    return arr
}

非递归算法

function inorderTraversal(root) {
    const arr = []
    const stack = []
    let p = root

    while (p || stack.length !== 0) {
        if (p) {
            stack.push(p)
            p = p.left
        } else {
            const q = stack.pop()
            arr.push(q.val)
            p = q.right
        }
    }

    return arr
}

后序遍历

递归算法

function postorderTraversal(root) {
    const arr = []

    function postorder(root) {
        if (!root) return
        postorder(root.left)
        postorder(root.right)
        arr.push(root.val)
    }

    postorder(root)

    return arr
}

非递归算法

非递归算法需要模拟栈，只不过栈中存放的是节点而不是函数。入栈和出栈的目的是为了访问该节点的其他子树（右子树）。

按照后序遍历的思路，需要一直找到二叉树最左边的节点（即从最底部开始访问），沿途把经过的左节点（也可以理解为每一棵子树的根节点）依次放入栈中，然后开始检视栈顶元素，根据具体情况，按照左右根的顺序访问。

和前序、中序遍历不同，后序遍历要求根节点被最后访问，也就是说根节点要最后出栈。让我们把栈中的每个节点都看作是一个子树的根节点，那么在检视栈顶元素时会有如下几种情况：

1. 没有左右子树，是个叶子节点，那么按照左右根的顺序，直接出栈并访问
2. 有左子树，没有右子树，但上次访问的节点就是左子树，那么按照左右根的顺序，也应该出栈并访问
3. 有左子树，也有右子树，但上次访问的节点就是右子树，那么按照左右根的顺序，也应该出栈并访问
4. 有左子树，也有右子树，但上次访问的节点是左子树，那么按照左右根的顺序，这次应该访问右子树，继续之前的逻辑

function postorderTraversal(root) {
    const arr = []
    const stack = []
    let p = root
    let last = null

    while(p) {
        stack.push(p)
        p = p.left
    }

    while(stack.length > 0) {
        const top = stack[stack.length - 1]
        if (
            (!top.left && !top.right) ||
            (last === top.left && !top.right) ||
            last === top.right
        ) {
            stack.pop()
            arr.push(top.val)
            last = top
        } else {
            p = top.right
            while(p) {
                stack.push(p)
                p = p.left
            }
        }
    }

    return arr
}

function postorderTraversal(root) {
    const arr = []
    const stack = []
    let p = root
    let last = null

    while(p || stack.length > 0) {
        // 一直深挖到最左边的节点
        if (p) {
            stack.push(p)
            p = p.left
        } else {
            // 左子树访问完毕，弹出栈顶元素，看看右子树的情况
            const top = stack.pop()
            // 没右子树，或者右子树上次已经访问完了，则可以访问该元素
            if (!top.right || top.right === last) {
                arr.push(top.val)
                // 标记最新访问的元素
                last = top
            } else {
                // 右子树还没访问，则将当前元素再放回去
                stack.push(top)
                // 开始访问右子树
                p = top.right
            }
        }
    }

    return arr
}

分析

如果去掉 push 语句，从递归的角度看，三种算法是完全相同的，或说这三种算法的访问路径是相同的，只是访问结点的时机不同。每个节点都会被经过三次，一次是刚进入这个节点，一次是其左子树遍历完成后返回，一次是其右子树遍历完成后返回。第一次经过时访问则是前序遍历，第二次经过时访问则是中序遍历，第三次经过时访问则是后序遍历。

三种遍历算法的时间复杂度均为 O(n)，因为每个节点都要被访问一遍；空间复杂度均为 O(n)，例如此二叉树是个左斜树，那么最高需要 n 层的栈。