二叉树前序遍历，中序遍历，后序遍历的统一模板写法【递归和非递归】

二叉树有三种深度遍历的方式，分别是前序，中序和后序，分别对应LeetCode的144，94，145三道题目。

三种遍历方式的递归写法都差不多，也比较容易，相信大家都已经烂熟于心了。

但是非递归写法，目前还有很多不同的写法，比如循环条件，有的用栈是否为空，有的用指针是否指向NULL。

这样比较混乱的形式，不利于我们理解和记忆，所以这里我总结了三种遍历的非递归统一形式的写法，可以当成一个模板，既便于理解，同时也方便记忆。

下面分别讲三种遍历的解法。

前序遍历

前序遍历即先访问根，再访问左节点，再访问右节点（VLR）。其递归写法如下：

public List<Integer> preorderTraversal(TreeNode root) {
    ArrayList<Integer> result = new ArrayList<>();  //初始化结果数组
    dfs(root, result);  // 进行DFS遍历
    return result;  //返回结果
}

private void dfs(TreeNode root, ArrayList<Integer> result) {
    if (root == null)    // 叶节点访问完毕后，到达null，结束递归
        return;
    result.add(root.val);   // 先把根节点的值加入结果
    dfs(root.left);  // 然后遍历左子树
    dfs(root.right);  // 接着右子树
}

递归写法比较容易理解，这里不做多的解释。接下来就是非递归写法了。非递归写法要用到栈来保存过程，其实有点像模拟函数调用递归栈的过程。 代码如下：

public List<Integer> preorderTraversal(TreeNode root) {
    ArrayList<Integer> result = new ArrayList<>(); //初始化结果数组
    Stack<TreeNode> stack = new Stack<>();  // 初始化栈

    TreeNode cur = root;  // cur指向当前结点

    while (cur != null || !stack.isEmpty()) {  // 循环条件：cur不为空 或者 栈不为空。 其中cur不为空的情况出现在：左节点和根节点都访问完毕时，当前指向根节点的右节点时，栈恰好为空，但是此时还未结束。
        if (cur != null) {  //当cur不为空时，先输出其值，再将其压栈（为了后面能够进入其右节点），再访问它的左节点。
            result.add(cur.val);
            stack.push(cur.right);
            cur = cur.left;
        }
        else {   //当cur为空时，弹栈。此时栈顶元素已经被访问且输出过，所以此次直接进入其右节点即可。
            cur = stack.pop();  
            cur = cur.right;
        }
    }
    return result;
}

代码已经有比较详细的注释，如果还是没有完全理解的话，建议你画一个二叉树，按照上面一步一步地走下去，加强理解。

你可能会觉得这种写法没有标答里面的简单。在标答里，循环条件用的是!stack.isEmpty()，也就是栈不为空，然后每次都会先执行push(cur.right), 再执行push(cur.left)，看起来很简单对吧，但是这种是仅对前序遍历有效的，对中序和后序遍历没有效果，所以我这里不建议使用这种写法。

中序遍历

接下来是中序遍历。中序遍历就是先访问左节点，再访问根节点，最后访问右节点（LVR）。这种稍微比前序遍历更复杂一点。 首先是递归写法。

public List<Integer> inorderTraversal(TreeNode root) {
    ArrayList<Integer> result = new ArrayList<>();

    dfs(root, result);
    return result;
}

private void dfs(TreeNode root, ArrayList<Integer> result) {
    if (root != null) {
        dfs(root.left, result);
        result.add(root.val);
        dfs(root.right, result);
    }
}

然后是非递归写法（与前序遍历的写法高度相似，仅几行代码的区别）

public List<Integer> inorderTraversal(TreeNode root) {
    ArrayList<Integer> result = new ArrayList<>(); //初始化结果数组
    Stack<TreeNode> stack = new Stack<>();  // 初始化栈

    TreeNode cur = root;  // cur指向当前结点

    while (cur != null || !stack.isEmpty()) {  // 循环条件：cur不为空 或者 栈不为空。 其中cur不为空的情况出现在：左节点和根节点都访问完毕时，当前指向根节点的右节点时，栈恰好为空，但是此时还未结束。
        if (cur != null) {  //当cur不为空时，将其压栈，再访问它的左节点。
            stack.push(cur);
            cur = cur.left;
        }
        else {   //当cur为空时，弹栈，值赋给cur。此时cur的左子树都已经访问过并且输出了，接下来应该输出cur，然后进入右子树。
            cur = stack.pop();  
            result.add(cur.val);
            cur = cur.right;
        }
    }
    return result;
}

仔细理解一下，是不是与前序遍历的写法高度相似！

后序遍历

接下来是后序遍历。首先还是给出递归写法

public List<Integer> postorderTraversal(TreeNode root) {
    ArrayList<Integer> result = new ArrayList<>();  //初始化结果数组
    dfs(root, result);  // 进行DFS遍历
    return result;  //返回结果
}

private void dfs(TreeNode root, ArrayList<Integer> result) {
    if (root == null)    // 叶节点访问完毕后，到达null，结束递归
        return;
    dfs(root.left);  // 先遍历左子树
    dfs(root.right);  // 接着右子树
    result.add(root.val);   // 然后根节点的值加入结果
}

然后是非递归写法。后序遍历的非递归写法，相比于前序遍历和中序遍历，要更加困难一些。因为前序遍历和中序遍历都可以在一个循环里，分两个分支，做确定的事情即可。而后序遍历不一样，后序遍历在遇到null弹栈的时候，有两种情况，一种是从左子树回来，此时不能像中序遍历一样直接弹栈，因为根节点要留着，等把右子树也访问完毕后再输出，所以此时要直接进入右子树，待右子树都输出之后再回来的时候才能弹出根节点，因此我们要知道当前是从左子树回去还是从右子树回去。这里我们用一个集合Set来存储已经从左子树回去过的根节点，因此下次从右子树回去的时候，就知道应该输出根了。 代码如下：

public List<Integer> postorderTraversal(TreeNode root) {
    ArrayList<Integer> result = new ArrayList<>(); //初始化结果数组
    Stack<TreeNode> stack = new Stack<>(); // 初始化栈
    Set<TreeNode> visited = new HashSet<>(); // 初始化集合，存放已经从左子树返回过的节点。

    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        if (cur != null) {  //当cur不为空时，将其压栈，再访问它的左节点。
            stack.push(cur);
            cur = cur.left;
        }
        else {   // 当cur为空时，需要分两种情况：从左子树返回、从右子树返回。
            TreeNode tmp = stack.peek();
            if (visited.contains(tmp)) {   //visited中已经有cur了，说明从右子树返回，可以输出根了。
                result.add(tmp.val);
                stack.pop();   // 记得这里一定要将cur弹出，因为上面是用的peek
            }
            else {     // visited中没有tmp，说明第一次返回，也就是从左子树返回的，因此标记访问后，直接进入右节点。
                visited.add(tmp);
                cur = tmp.right;
            }
        }
    }
    return result;
}

总结 以上的三种写法，都有相同的循环条件和判断条件，只不过后序遍历要更复杂一点，要多一次判断。个人感觉这种非递归的写法模板，容易理解，方便记忆，希望给你带来帮助。