【数据结构与算法】二叉树深度优先遍历（非递归版）

在文章「数据结构与算法」二叉树中写了递归版本的深度优先遍历的代码，本篇写非递归版。

非递归版本的核心思路其实就是使用栈来实现，递归的底层其实就是栈，使用递归无需我们自己去关系入栈和出栈的具体操作，非递归版本则需要自己使用栈这种数据结构，并且自行处理出入栈。

前序遍历

回顾下递归代码：

分析下它是如何走的，仔细思考下图：

上图是递归代码的执行顺序，每个节点都会执行一次preOrderDfs方法，当节点不为空的时候会将节点压入栈中，当是空的时候，执行递归中的归操作，节点出栈。

那么我们就可以使用栈这种数据结构来模拟：

1. 从根节点1开始循环，如果节点不是空的话，将其加入到栈中，一直会将1、2、4顺序压入栈中，直到节点的值是空，比如红线3。
2. 此时节点等于空，因为此时要遍历右子树，那么必须找到父节点，才能通过.right获取其右子树的根节点，那么父节点在哪呢？在栈中。（特别说明，此时node == null，但是栈中还有元素）。

代码如下：

public static void dfs(TreeNode node) {
    Deque<TreeNode> stack = new LinkedList<>();
    while (node != null || !stack.isEmpty()) {
        if (node != null) { // 如果节点不为空，入栈
            stack.push(node); // 入栈
            // 前序遍历
            System.out.println(node.val + "\t");
            // 处理左子树
            node = node.left;
        } else {
            TreeNode pop = stack.pop();
            node = pop.right; // 处理右子树
        }
    }
}

中序遍历

中序遍历其实经历的路径与前序遍历经历的路径是相同的，我们只需要打印出栈的节点值就是中序遍历的结果，代码如下：

public static void dfs(TreeNode node) {
    Deque<TreeNode> stack = new LinkedList<>();
    while (node != null || !stack.isEmpty()) {
        if (node != null) { // 如果节点不为空，入栈
            stack.push(node); // 入栈
            // 前序遍历
            // System.out.println(node.val + "\t");
            // 处理左子树
            node = node.left;
        } else {
            TreeNode pop = stack.pop();
            // 中序遍历
            System.out.println(pop.val + "\t");
            node = pop.right; // // 处理右子树
        }
    }
}

后序遍历

后续遍历向下遍历的时候代码与前序和中序思想相同，代码也相同，回的时候则有些不同，在前序遍历和中序遍历的地方当节点为空的时候，首先是出栈栈顶元素的，但是在后续遍历中则不可以，为什么呢？因为后序遍历是在最后输出子树的根节点，如果弹栈则找不到根节点了，换句话说，如果一个节点的左右子树都处理完了才能弹栈。

比如，如下图：

如果此时节点5输出完毕，此时栈顶元素一定是3，按照后续遍历的要求，一定要先输出节点6，我们可以通过栈顶元素3来得到6，并输出，接下来要输出3，但是如果节点3已经被弹出了，则找不到了，所以先不能弹出，如果需要使用我们只能通过peek获取，接下来要处理右子树了，也就是根节点6的树，此时分为两种情况：

情况1：这个节点6跟上图不同，是个空的，那么说明右子树已经处理完毕了，可以弹栈。

情况2：这个节点6跟上图一样，不是个空的，那么如何判断这个右子树处理完毕了呢？我们反方向考虑下，如果节点6处理完毕，然后将其弹栈，接下来肯定要处理节点3了，如果我们记录下上次弹栈的节点lastPop，如果lastPop = 当前节点3.right的话，说明右子树已经处理完毕。

我们看下实际代码：

public static void dfs(TreeNode node) {
    Deque<TreeNode> stack = new LinkedList<>();
    TreeNode lastPop = null; // 最后一次弹栈元素
    while (node != null || !stack.isEmpty()) {
        if (node != null) { // 如果节点不为空，入栈
            stack.push(node); // 入栈
            // 前序遍历
            // System.out.println(node.val + "\t");
            // 处理左子树
            node = node.left;
        } else {
            TreeNode peek = stack.peek();
            if (peek.right == null || lastPop == peek.right) { // 右子树无需处理或者已经处理完毕
                lastPop = stack.pop();
                // 后序遍历
                System.out.printf(lastPop.val + "\t");
            } else {
                node = peek.right; // 处理右子树
            }
        }
    }
}

三种遍历合并代码

我们可以将三种遍历融合到一起，使用一套代码，对比上面的三种代码，我们可以发现，三种代码中前序遍历的代码完全一致，不同的是中序和后序遍历的代码。

后序遍历的处理更加麻烦，没办法，我们只能将中序遍历融合到后序遍历的代码中，上面后序遍历中其实有三种情况：当前节点无右子树无需处理、当前节点有右子树已经处理完毕、处理右子树，上述代码中条件代码的三种情况。

1. 当前节点无右子树无需处理：对于中序遍历：要先打印栈顶元素的值，然后再弹出栈顶元素（也可先弹栈，后打印，没有影响）；对于后序遍历，要弹出栈顶元素，然后打印该元素的值。
2. 当前节点有右子树已经处理完：对于中序遍历：无需打印；对于后序遍历：要弹出栈顶元素，然后打印该元素的值。
3. 左子树处理完毕要处理右子树：对于中序遍历：在处理右子树之前应该打印栈顶元素的值，后序遍历则不用打印。

最终合并的代码如下：

public static void dfs(TreeNode node) {
    Deque<TreeNode> stack = new LinkedList<>();
    TreeNode lastPop = null;
    while (node != null || !stack.isEmpty()) {
        if (node != null) { // 如果节点不为空，入栈
            stack.push(node); // 入栈
            // 前序遍历
            // System.out.println(node.val + "\t");
            node = node.left;
        } else {
            TreeNode peek = stack.peek();
            if (peek.right == null) { // 右子树无需处理或者已经处理完毕
                lastPop = stack.pop();
                // 中序遍历
                // System.out.printf(lastPop.val + "\t");
                // 后序遍历
                //System.out.printf(lastPop.val + "\t");
            } else if (lastPop == peek.right) {
                lastPop = stack.pop();
                // 后序遍历
                // System.out.printf(lastPop.val + "\t");
            } else {
                // 中序遍历
                // System.out.printf(peek.val + "\t");
                node = peek.right;
            }
        }
    }
}

上面的代码就是整合后的代码，可以根据需求在不同的地方处理即可（前中后序遍历出的代码都注释了）。