LeetCode 94.二叉树的中序遍历

这篇具有很好参考价值的文章主要介绍了LeetCode 94.二叉树的中序遍历。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目描述

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

示例 1:

LeetCode 94.二叉树的中序遍历,Leetcode hot 100,leetcode,算法,java

输入:root = [1,null,2,3]
输出:[1,3,2]

示例 2:

输入:root = []
输出:[]

示例 3:

输入:root = [1]
输出:[1]

提示:

  • 树中节点数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100
  • 给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。

    示例 1:

    LeetCode 94.二叉树的中序遍历,Leetcode hot 100,leetcode,算法,java

    输入:root = [1,null,2,3]
    输出:[1,3,2]
    

    示例 2:

    输入:root = []
    输出:[]
    

    示例 3:

    输入:root = [1]
    输出:[1]
    

    提示:

  • 树中节点数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

方法一 递归

思路:

很基础的,中序遍历指的是根节点在中间。左—根—右的顺序。

代码:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res=new ArrayList<Integer>();
        zhongxu(root,res);
        return res;
    }
    public void zhongxu(TreeNode root,List<Integer> res){
        if(root ==null) return ;
        zhongxu(root.left,res);
        res.add(root.val);
        zhongxu(root.right,res);
    }
}

方法二 迭代

思路:

第一次学到这个迭代的思想,其实就是用了应该栈来模拟递归,又或者说递归其实隐式地用了一个栈。

先把左节点一个一个全部压入栈,直到没有左节点了。然后弹出栈顶(最左的节点),处理完了,把它的右节点压入栈。

代码:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res=new ArrayList<Integer>();
        Deque<TreeNode> stk=new LinkedList<TreeNode>();
        while(root!=null||!stk.isEmpty()){
            while(root!=null){
                stk.push(root);
                root=root.left;
            }
            root=stk.pop();
            res.add(root.val);
            root=root.right;
        }
        return res;
    }
}

 学到Java的栈,一般不用Stack,用Deque。因为Stack慢吧。

Deque可以当队列用,也可以当栈用。

队列:offer()    poll()       peek()

栈:push()      poll()/pop()      peek()

参考链接:94. 二叉树的中序遍历 - 力扣(LeetCode)文章来源地址https://www.toymoban.com/news/detail-861421.html

到了这里,关于LeetCode 94.二叉树的中序遍历的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【力扣】94、二叉树的中序遍历

    注:二叉树的中序遍历:左根右;

    2024年02月12日
    浏览(15)
  • 94. 二叉树的中序遍历(递归+迭代)

    题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 解题思路:  方法一:递归 中序遍历的操作定义为,若二叉树为空,则空操作,否则: 中序遍历左子树 访问根节点 中序遍历右子树 AC代码  方法二:迭代,递归的循环版本,借助栈来完成递归, 如果root !=nul

    2024年02月07日
    浏览(22)
  • 力扣(144. 二叉树的前序遍历&&94.二叉树的中序遍历&&145. 二叉树的后序遍历)

    题目链接 题目1: 思路:较简单的思路,就是先将左孩子全部入栈,然后出栈访问右孩子,右孩子为空,再出栈,不为空,右孩子入栈,然后再次循环访问左孩子。 题目链接 题目2: 思路:同前序遍历一样,只不过访问结点,改为出栈时访问。 题目3链接 题目3: 思路1:同样

    2024年01月19日
    浏览(17)
  • LeetCode 0094.二叉树的中序遍历:递归/迭代(栈模拟递归)

    力扣题目链接:https://leetcode.cn/problems/binary-tree-inorder-traversal/ 给定一个二叉树的根节点 root ,返回 它的 中序  遍历 。   示例 1: 示例 2: 示例 3:   提示: 树中节点数目在范围 [0, 100] 内 -100 = Node.val = 100   进阶:  递归算法很简单,你可以通过迭代算法完成吗? 写一个函数

    2024年02月20日
    浏览(10)
  • 算法D14 | 二叉树1 | 144. 二叉树的前序遍历 145. 二叉树的后序遍历 94. 二叉树的中序遍历

    理论基础  需要了解 二叉树的种类,存储方式,遍历方式 以及二叉树的定义  文章讲解: 二叉树既可以链式存储(利用指针,类似栈和队列),也可以用数组表示。 深度优先遍历 前序遍历(递归法,迭代法) 中序遍历(递归法,迭代法) 后序遍历(递归法,迭代法)

    2024年02月20日
    浏览(11)
  • LeetCode 144. 94. 145. 二叉树的前序,中序,后续遍历(详解) ੭ ᐕ)੭*⁾⁾

    目录 144.二叉树的前序遍历 一. TreeSize函数的实现: 二. preOrderTree函数的实现: 三.preorderTraversal函数的实现:  最后完整代码: 94.二叉树的中序遍历:  145.二叉树的后续遍历: 经过前面的二叉树的学习,现在让我们实操来练练手~如果对二叉树还不熟悉的小伙伴可以看看我的

    2024年01月22日
    浏览(13)
  • 算法练习第13天|递归实现 144.二叉树的前序遍历(opens new window)145.二叉树的后序遍历(opens new window)94.二叉树的中序遍历

    二叉树的存储方式:链式存储和顺序存储。链式存储用指针,顺序存储用数组。其结构如下图所示。 链式存储: 顺序存储: 顺序存储时,若父节点下表为i,则其左孩子下标为 2*i + 1,右孩子下标为2*i + 2. 二叉树主要有两种遍历方式: 深度优先遍历:先往深走,遇到叶子节点

    2024年02月22日
    浏览(16)
  • 二叉树题目:二叉树的中序遍历

    标题:二叉树的中序遍历 出处:94. 二叉树的中序遍历 3 级 要求 给你二叉树的根结点 root texttt{root} root ,返回其结点值的中序遍历。 示例 示例 1: 输入: root   =   [1,null,2,3] texttt{root = [1,null,2,3]} root = [1,null,2,3] 输出: [1,3,2] texttt{[1,3,2]} [1,3,2] 示例 2: 输入: root   =  

    2024年02月09日
    浏览(18)
  • 【力扣 - 二叉树的中序遍历】

    给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。 树中节点数目在范围 [0, 100] 内 首先我们需要了解什么是二叉树的中序遍历:按照访问左子树——根节点——右子树的方式遍历这棵树,而在访问左子树或者右子树的时候我们按照同样的方式遍历,直到遍历完整棵树。因

    2024年02月22日
    浏览(13)
  • 树的前序遍历与中序遍历构造二叉树和树的中序遍历与后序遍历构造二叉树

    目录 一.树的前序遍历与中序遍历构造二叉树 1.题目描述 2.问题分析 3.代码实现 二.树的中序遍历与后序遍历构造二叉树 1.题目描述 2.问题分析 3.代码实现 三.问题思考 给定两个整数数组  preorder 和 inorder  ,其中  preorder 是二叉树的 先序遍历 , inorder  是同一棵树的 中序遍

    2023年04月15日
    浏览(12)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包