二叉树oj ----＞中序遍历（非递归）

柔情只为你懂 2023-10-02 14:02 41阅读 0赞

题目内容：  
![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_20_color_FFFFFF_t_70_g_se_x_16][]

解题思路：

> 主要的思路和之前的先序遍历差不多，也是利用栈的特性，不同的地方也比较小
> 
>  *  首先遍历根节点的左子树，直到左子树为空时，遍历当前结点，中序遍历的顺序是（左子树 根节点 右子树），不能直接先遍历结点，所以，这次需要保存的是当前结点

解题代码：

class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> list = new ArrayList<>();
    
            if(root == null){
                return list;
            }
            Stack<TreeNode> s = new Stack<>();
            TreeNode cur = root;
            while(!s.empty() || cur != null){
                //先往左子树遍历
                while(cur != null){
                    s.push(cur);
                    cur = cur.left;
                }
    
                cur = s.pop();
                list.add(cur.val);
                cur = cur.right;
            }
            return list;
        }
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/8bcd148fbe5b4311aac4c833a758d547.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAb2hhbmHvvIE=,size_20,color_FFFFFF,t_70,g_se,x_16

发表评论取消回复

表情：

评论列表（有 0 条评论，41人围观）

还没有评论，来说两句吧...

相关阅读

相关二叉树后序遍历(非递归)

叉树的递归遍历算法就不用说了；在非递归算法中，后序遍历难度大，很多书上只给出思想或者几段无法直接调试的代码，甚至有些书上是错的，当时我在研究的过程中，就是按着书上错误的代...

深藏阁楼爱情的钟/ 2024年04月17日 22:41/ 0 赞/ 155 阅读

相关二叉树oj ——＞后序遍历（非递归）

题目要求： ![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_

Love The Way You Lie/ 2023年10月02日 14:02/ 0 赞/ 87 阅读

相关二叉树oj ----＞中序遍历（非递归）

题目内容： ![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size

柔情只为你懂/ 2023年10月02日 14:02/ 0 赞/ 42 阅读

相关二叉树oj ----＞先序 or 前序遍历（非递归实现）

题目内容： ![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_

「爱情、让人受尽委屈。」/ 2023年10月02日 14:00/ 0 赞/ 34 阅读

相关二叉树的中序遍历(非递归)

二叉树的中序遍历 > 题目描述: > > 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。 > > 给定一个二叉树，

红太狼/ 2023年05月31日 07:25/ 0 赞/ 212 阅读

相关二叉树中序遍历 -- 递归和非递归实现

/ 实现二叉树中序遍历 -- 采用递归和非递归方法经调试可直接运行源码如下 / include <stdio.h>

古城微笑少年丶/ 2022年07月27日 11:56/ 0 赞/ 253 阅读

相关先序遍历、中序遍历二叉树非递归实现

先序遍历 [leetcode 144. binary-tree-preorder-traversal][] / Definition for a binary

柔情只为你懂/ 2022年07月16日 03:21/ 0 赞/ 342 阅读

相关非递归中序遍历二叉树

/非递归中序遍历二叉树/ include<stdio.h> define maxsize 100 typedef char datatype;

╰半夏微凉°/ 2022年06月15日 00:22/ 0 赞/ 338 阅读

相关非递归先序遍历二叉树

/非递归先序遍历二叉树/ include<stdio.h> define maxsize 100 typedef char datatype;

绝地灬酷狼/ 2022年06月15日 00:18/ 0 赞/ 322 阅读

相关二叉树—前序遍历、中序遍历(非递归)

【转载】https://www.cnblogs.com/bigsai/p/11393609.html 层级遍历 public void cengxu(node t

朱雀/ 2021年09月18日 05:06/ 0 赞/ 529 阅读