【数据结构】二叉树的三种遍历（非递归讲解）

目录

1、前言

2、二叉树的非递归遍历

2.1、先序遍历

2.2、中序遍历

2.3、后序遍历

1、前言

学习二叉树的三种非递归遍历前，首先来了解一下递归序：

递归序就是按照先序遍历的顺序，遇到的所有结点按顺序排列，重复的结点也必须记录。

我们可以发现递归序中每个结点都会遇到三次。

这是因为当进入某一结点时，对该结点进行第一次操作，然后调用其左孩子结点，等左孩子结点结束调用时会返回自己，此时就可以对自己进行第二次操作，然后再调用其右孩子结点，等左孩子结点结束调用时又会返回自己，此时就可以对自己进行第三次操作，因为不管怎样，调用完孩子结点后终究会返回到父结点。

直接给出结论：

递归序中第一次遇到该节点时打印结点，第二次第三次均不做任何操作，这就是先序遍历。

递归序中第二次遇到该节点时打印结点，第一次第三次均不做任何操作，这就是中序遍历。

递归序中第三次遇到该节点时打印结点，第一次第二次均不做任何操作，这就是后序遍历。

关于递归序详细的讲解，可以看我之前写的一篇博客，里面有详细讲解，这里就不过多赘述：

【算法与数据结构】二叉树的三种遍历代码实现（上）—— 用递归序知识点讲解-CSDN博客https://blog.csdn.net/zzzzzhxxx/article/details/133609612?spm=1001.2014.3001.5501

2、二叉树的非递归遍历

任何递归函数都可以改成非递归函数，因为递归函数不是什么玄学，只是递归时系统帮忙解决了压栈问题。那么不用递归方式的话只要自己手动进行压栈依然可以完成递归能够实现的功能。

有了上面递归序的知识点作为铺垫，就可以很好的理解非递归的实现了。

2.1、先序遍历

递归序中第一次遇到该节点时打印结点，第二次第三次均不做任何操作，这就是先序遍历。

首先使用cur依次将二叉树所有左边界节点入栈，并且打印节点。当此时cur走到叶子节点后，将栈顶元素出栈，并让cur指向出栈元素的右孩子，继续进行左边界节点入栈操作。

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new LinkedList<>();
        if(root == null) {
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()) {
            if(cur != null) {
                stack.push(cur);
                System.out.print(cur.val + " ");  //第一次遇到时进行打印
                cur = cur.left;
            } else {
                cur =  stack.pop();   //第二次遇到
                cur = cur.right;
            }
        }
        return list;
    }

2.2、中序遍历

递归序中第二次遇到该节点时打印结点，第一次第三次均不做任何操作，这就是中序遍历。 

首先使用cur依次将二叉树所有左边界节点入栈。当此时cur走到叶子节点后，将栈顶元素出栈后并打印，此时第二次遇到该元素。然后让cur指向出栈元素的右孩子，继续进行左边界节点入栈操作。

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new LinkedList<>();
        if(root == null) {
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()) {
            if(cur != null) {
                stack.push(cur);   //第一次遇到
                cur = cur.left;
            } else {
                cur =  stack.pop();
                System.out.print(cur.val + " ");   //第二次遇到时进行打印
                cur = cur.right;
            }
        }
        return list;
    }

2.3、后序遍历

递归序中第三次遇到该节点时打印结点，第一次第二次均不做任何操作，这就是后序遍历。

首先使用cur依次将二叉树所有左边界节点入栈。当此时cur走到叶子节点后，使用peek()查找出栈顶元素top（并非出栈）后并打印，然后判断top节点是否存在右孩子，当存在时则让cur指向top节点的右孩子，继续进行左边界节点入栈操作。当top不存在右孩子时则将栈顶元素出栈并打印栈顶元素，此时第三次遇到该元素。

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new LinkedList<>();
        if(root == null) {
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode prev = null;
        while(cur != null || !stack.isEmpty()) {
            if(cur != null) {
                stack.push(cur);   //第一次遇到
                cur = cur.left;
            } else {
                TreeNode top = stack.peek();   //第二次遇到
                if(top.right != null && prev != top.right) {   //当该节点右子树不为空,并且之前没有去过右子树时
                    cur = top.right;						
                } else {     //该节点右子树为空或者是已经去过一次右子树了
                    top = stack.pop();
                    System.out.print(cur.val + " ");   //第三次遇到时进行打印
                    prev = top;
                }
            }
        }
        return list;
    }

博主推荐： 

【LeetCode力扣】单调栈解决Next Greater Number（下一个更大值）问题-CSDN博客https://blog.csdn.net/zzzzzhxxx/article/details/136030138?spm=1001.2014.3001.5501 【数据结构】二叉搜索树的模拟实现-CSDN博客https://blog.csdn.net/zzzzzhxxx/article/details/135910604?spm=1001.2014.3001.5501

 【LeetCode力扣】面试题 17.14. 最小K个数（top-k问题）-CSDN博客https://blog.csdn.net/zzzzzhxxx/article/details/135737266?spm=1001.2014.3001.5501

如果觉得作者写的不错，求给博主一个大大的点赞支持一下，你们的支持是我更新的最大动力！

如果觉得作者写的不错，求给博主一个大大的点赞支持一下，你们的支持是我更新的最大动力！

如果觉得作者写的不错，求给博主一个大大的点赞支持一下，你们的支持是我更新的最大动力！