二叉树的非递归遍历

妖狐艹你老母 2023-10-10 15:07 4阅读 0赞

![ced485cbb11e458d81a746890b32cf3f.gif][]

> 作者：敲代码の流川枫
> 
> 博客主页：[流川枫的博客][Link 1]
> 
> 专栏：[和我一起学java][java]
> 
> 语录：Stay hungry stay foolish
> 
> [Apifox = Postman + Swagger + Mock + JMeter。集接口文档工具、接口Mock工具、接口自动化测试工具、接口调试工具于一体,提升 10 倍研发效率][Apifox _ Postman _ Swagger _ Mock _ JMeter_Mock_ 10]

**文章目录**

1.前序遍历

2.中序遍历

3.后序遍历

--------------------

二叉树用递归来进行遍历是很简单的，就几行代码，今天总结一下如何进行非递归遍历

## 1.前序遍历 ##

给你二叉树的根节点 `root` ，返回它节点值的 **前序**遍历。

![7ae960b1f3d443e4b3adfd7439be2b60.png][]

![030b90890201431281ab1d157b8b4af2.png][]

思路

用迭代的方式实现递归函数解法，两种方式是等价的，区别在于递归的时候隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来，其余的实现与细节都相同

代码

class Solution {
       
        public List<Integer> preorderTraversal(TreeNode root) {
            Stack<TreeNode> stack = new Stack<>();
            List<Integer> ret = new ArrayList<>(); 
            TreeNode cur = root; 
            //最外层循环是最后才加上去的，开始写的时候想不到这个循环条件
            while(cur != null || !stack.isEmpty()){
                while(cur != null){
                    stack.push(cur);
                    System.out.print(cur.val+" ");
                    ret.add(cur.val);
                    cur = cur.left;
                }
                TreeNode top = stack.pop();
                cur = top.right;
            }
            return ret;
        }
    }

时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。

空间复杂度：O(n)，为迭代过程中显式栈的开销，平均情况下为 O(logn)，最坏情况下树呈现链状，为 O(n)。

## 2.中序遍历 ##

给定一个二叉树的根节点 `root` ，返回 *它的 **中序** 遍历* 。

![be86e4a77df640c89096215b29092af5.png][]

代码

class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
           List<Integer> ret = new ArrayList<>();
           TreeNode cur = root;
           Stack<TreeNode> stack = new Stack<>();
           while(cur != null || !stack.isEmpty()){
               while(cur != null){
                   stack.push(cur);
                   cur = cur.left;
               }
               TreeNode top = stack.pop();
                ret.add(top.val);
                cur = top.right;
           }
           return ret;
        }
    }

## 3.后序遍历 ##

给你一棵二叉树的根节点 `root` ，返回其节点值的 **后序遍历** 。![a5008fd3232941049bc16d16db906aa5.png][]

思路

和前面遍历思路相同，只需要注意根节点入表的判断条件，这里用了prev标记，避免死循环

代码

class Solution {
        public List<Integer> postorderTraversal(TreeNode root) {
            List<Integer> ret = new ArrayList<>();
           //当前节点
           TreeNode cur = root;
           //用来标记上一个被打印的节点
           TreeNode prev = null;
           Stack<TreeNode> stack = new Stack<>();
           while(cur != null || !stack.isEmpty()){
               while(cur != null){
                   stack.push(cur);
                   cur = cur.left;
               }
               TreeNode top = stack.peek();
               //或者后面表示已经被打印过了，如果top.right打印过了，
    就继续弹出top，而不是cur = top.right陷入死循环
               if(top.right == null || top.right == prev){
                   ret.add(top.val);
                   stack.pop();
                   prev = top;
               }else{
                   cur = top.right;
               }
           }
           return ret;
        }
    }

时间复杂度：O(n)，其中 n 是二叉搜索树的节点数。每一个节点恰好被遍历一次

空间复杂度：O(n)，为迭代过程中显式栈的开销，平均情况下为 O(\\log n)，最坏情况下树呈现链状，为 O(n)

[ced485cbb11e458d81a746890b32cf3f.gif]: https://img-blog.csdnimg.cn/ced485cbb11e458d81a746890b32cf3f.gif
[Link 1]: https://blog.csdn.net/chenchenchencl?spm=1011.2421.3001.5343
[java]: https://blog.csdn.net/chenchenchencl/category_11932758.html
[Apifox _ Postman _ Swagger _ Mock _ JMeter_Mock_ 10]: http://apifox.cn/a103liucf
[7ae960b1f3d443e4b3adfd7439be2b60.png]: https://img-blog.csdnimg.cn/7ae960b1f3d443e4b3adfd7439be2b60.png
[030b90890201431281ab1d157b8b4af2.png]: https://img-blog.csdnimg.cn/030b90890201431281ab1d157b8b4af2.png
[be86e4a77df640c89096215b29092af5.png]: https://img-blog.csdnimg.cn/be86e4a77df640c89096215b29092af5.png
[a5008fd3232941049bc16d16db906aa5.png]: https://img-blog.csdnimg.cn/a5008fd3232941049bc16d16db906aa5.png