JavaScript算法套路之二叉树的前、中、后序迭代遍历

递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。所以。我们用栈当然就能实现同样的遍历了。

栈的特点是先进性后出,所以在遍历二叉树的时候，要反过来遍历，比如前序遍历，正常情况下，应该是中，左，右，那么我们的遍历顺序就应该是中，右，左，出栈的时候正好是中，左，右。下面我们来实现以下前序遍历：

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */

const preorderTraversal = (root) => {
    const result = [];
    //  判断，如果没有root了，就返回结果
    if (!root) return result;
    //  把中间节点放入道栈中
    const stack = [root];
    let cur = null;
    while (stack.length) {
        cur = stack.pop();
        result.push(cur.val);
        cur.right && stack.push(cur.val);
        cur.left && stack.push(cur.val);
    }
    return result;
};

这就是迭代方法的前序遍历，那既然能写出来前序遍历，那二叉树的后续遍历是不是也就可以自然而然的写出来了呢？与前序遍历不同的是：先序遍历是中左右，后续遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */

const backOrder = (root) => {
    let result = [];
    if (!root) return result;
    let stack = [root];
    let cur = null;
    do {
        cur = stack.pop();
        result.push(cur.val);
        cur.left && stack.push(cur.val);
        cur.right && stack.push(cur.val);
    } while (stack.length)
    return result.reverse();
};

这个时候，你会不会觉得中序遍历和前序、后续遍历也很相似呢？其实不然，中序遍历的顺序是左中右,要先遍历二叉树的顶部节点，然后再遍历一层一层的向下访问，直到左枝叶的最底部，再开始处理节点。那么这个时候，就需要使用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。来看代码：

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */

const midOrder = (root) => {
    let stack = [];
    let result = [];
    let cur = root;
    while (stack.length || cur) {
        if (cur) {
            stack.push(cur);
            cur = cur.left;
        } else {
            stack.pop();
            result.push(cur.val);
            cur = cur.right;
        }
    }
    return result;
};

写了这么多的代码，好像有点乱，那就二叉树的前、中后序迭代遍历能不能总结个套路呢？当然没问题的啦。。。我们怎么做呢？看：我们将要处理的节点放入到栈中，紧接着放入一个空指针作为标记。上代码：

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */

//  前序遍历
const preOrder = (root) => {
    let result = [];
    let stack = [];
    if (root) {
        stack.push(root);
    }
    while (stack.length) {
        let cur = stack.pop();
        if (!cur) {
            result.push(stack.pop().val);
            continue;
        }
        if (cur.right) stack.push(cur.right);
        if (cur.left) stack.push(cur.left)
        stack.push(cur);
        stack.push(null);
    }
    return result;
}

//  中序遍历
const midOrder = (root) => {
    let result = [];
    let stack = []
    if (root) stack.push(root);
    while (stack.length) {
        let cur = stack.pop();
        if (!cur) {
            result.push(stack.pop());
            continue;
        }
        if (cur.right) stack.push(cur.right);
        stack.push(cur);
        stack.push(null);
        if (cur.left) stack.push(cur.left);
    }
    return result;
}

//  后序遍历
let backOrder = (root) => {
    let result = [];
    let stack = [];
    if (root) stack.push(root);
    while (stack.length) {
        let cur = stack.pop();
        if (!cur) {
            result.push(stack.pop());
            continue;
        }
        stack.push(cur);
        stack.push(null);
        if (cur.right) stack.push(cur.right);
        if (cur.left) stack.push(cur.left);
    }
    return result;
}

理解很重要。。。。