LeetCode 94 二叉树的中序遍历

题目描述

二叉树的中序遍历

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

示例 1:

在这里插入图片描述

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

示例 2:

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

示例 3:

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

提示:

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

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

解法

解法1:递归

按照访问左子树——根节点——右子树的方式遍历这棵树,而在访问左子树或者右子树的时候我们按照同样的方式遍历,直到遍历完整棵树。因此整个遍历过程天然具有递归的性质,我们可以直接用递归函数来模拟这一过程。

java代码:

/**
 * 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>();
        inorder(root, res);
        return res;
    }

    private void inorder (TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        // 先左遍历
        inorder(root.left, res);
        res.add(root.val);
        inorder(root.right, res);
    }
}

复杂度

  • 时间复杂度:O(n) ,其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。
  • 空间复杂度:O(n),空间复杂度取决于递归的栈深度,而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。

解法2:迭代

方法一的递归函数我们也可以用迭代的方式实现,两种方式是等价的,区别在于递归的时候隐式地维护了一个栈,而我们在迭代的时候需要显式地将这个栈模拟出来,其他都相同,具体实现可以看下面的代码。

java代码:

/**
 * 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;
    }

}

复杂度

  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/543876.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Composite 组合

意图 将对象组合成树形结构以表示“部分-整体”的层级结构。Composite使得用户对单个对象和组合对象的使用具有一致性。 结构 其中&#xff1a; Component为组合中的对象声明接口&#xff1b;在适当情况下实现所有类共有接口的默认行为&#xff1b;声明一个接口用于访问和管…

Spring Boot(二)— 自定义Spring Boot Starter

在Spring Boot中&#xff0c;自定义Spring Boot Starter是一个常见且强大的功能&#xff0c;它允许开发者为特定的功能或库创建自己的自动配置&#xff0c;从而简化集成过程。 1 前置知识 Spring Boot的事件为应用的启动和关闭提供了详细的上下文信息&#xff0c;使得开发者能…

OSI七层网络模型 —— 筑梦之路

在信息技术领域&#xff0c;OSI七层模型是一个经典的网络通信框架&#xff0c;它将网络通信分为七个层次&#xff0c;每一层都有其独特的功能和作用。为了帮助记忆这七个层次&#xff0c;有一个巧妙的方法&#xff1a;将每个层次的英文单词首字母组合起来&#xff0c;形成了一句…

腾讯云优惠券详细介绍及领券步骤详解

随着云计算技术的不断发展和普及&#xff0c;越来越多的企业和个人开始选择使用云服务来满足自身的需求。腾讯云作为国内领先的云服务提供商&#xff0c;以其稳定、高效、安全的服务赢得了广大用户的信赖。为了回馈广大用户&#xff0c;腾讯云经常推出各种优惠活动&#xff0c;…

【JS】数组交换位置

公式 arr.splice(oldIndex, delCount, ...arr.splice(newIndex, delCount, arr[oldIndex])) arr - 操作的数组delCount - 删除的数组个数oldIndex - 交换位置的数组下标1newIndex - 交换位置的数组下标2...arr - 提取数组里的元素 splice删除元素时&#xff0c;返回一个数组&a…

利用计算机视觉算法提取裂纹相关特征参数信息

ABCnutter/CrackFeature: &#x1f680;使用计算机视觉相关算法提取裂缝的骨架&#xff08;矢量化&#xff09;、轮廓【支持提前修复断裂裂缝】&#xff0c;以及几何特征参数&#xff08;长度、宽度、面积和主要方向&#xff09;【欢迎Star】。主要流程以及相关算法如下&#x…

异构超图嵌入的图分类 笔记

1 Title Heterogeneous Hypergraph Embedding for Graph Classification&#xff08;Xiangguo Sun , PictureHongzhi Yin , PictureBo Liu , PictureHongxu Chen , PictureJiuxin Cao , PictureYingxia Shao , PictureNguyen Quoc Viet Hung&#xff09;【WSDM 2021】 2 Co…

1038: 顺序表中重复数据的删除

解法&#xff1a; #include<iostream> #include<vector> #include<algorithm> using namespace std; int main() {int n, k;cin >> n;vector<int> arr(n);for (auto& x : arr) cin >> x;cin >> k;int sum 0;for (auto x : arr…

句柄ros::NodeHandle nh(“~“)与nh对launch文件参数配置(param)的影响

ros::NodeHandle nh("~"); 改为&#xff1a; ros::NodeHandle nh; 即可 /*************************分割线 ************************/ 如果原本是&#xff1a; ros::NodeHandle nh;可以改成&#xff1a; ros::NodeHandle nh("~"); 试试

反射与动态代理

一、反射 什么是反射? 反射允许对成员变量&#xff0c;成员方法和构造方法的信息进行编程访问 1.获取class对象的三种方式 Class这个类里面的静态方法forName&#xff08;“全类名”&#xff09;&#xff08;最常用&#xff09; 通过class属性获取 通过对象获取字节码文件对…

浏览器原理---事件循环

浏览器原理 学习浏览器原理对于我们开发是很有必要的 我们可以了解到浏览器内部工作原理对自己的代码进行优化 进程线程 首先了解进程和线程 进程就就是内存在正在进行的应用程序 在内存中独占一个内存空间 并且进程之间是隔离的 可以看到每个应用都有一个进程 占用空间内存…

【300套】基于Springboot+Vue的Java毕业设计项目(附源码+演示视频+LW)

大家好&#xff01;我是程序猿老A&#xff0c;感谢您阅读本文&#xff0c;欢迎一键三连哦。 &#x1f9e1;今天给大家分享300的Java毕业设计&#xff0c;基于Springbootvue框架&#xff0c;这些项目都经过精心挑选&#xff0c;涵盖了不同的实战主题和用例&#xff0c;可做毕业…

【C++进阶】RAII思想&智能指针

智能指针 一&#xff0c;为什么要用智能指针&#xff08;内存泄漏问题&#xff09;内存泄漏 二&#xff0c;智能指针的原理2.1 RAII思想2.2 C智能指针发展历史 三&#xff0c;更靠谱的shared_ptr3.1 引用计数3.2 循环引用3.3 定制删除器 四&#xff0c;总结 上一节我们在讲抛异…

Vulnhub靶机 DC-1渗透详细过程

Vulnhub靶机:DC-1渗透详细过程 目录 Vulnhub靶机:DC-1渗透详细过程一、将靶机导入到虚拟机当中二、攻击方式主机发现端口扫描web渗透利用msf反弹shell数据库信息web管理员密码提权 一、将靶机导入到虚拟机当中 靶机地址&#xff1a; https://www.vulnhub.com/entry/dc-1-1,29…

Open CASCADE学习|BRepOffsetAPI_DraftAngle

BRepOffsetAPI_DraftAngle 是 Open CASCADE Technology (OCCT) 中用于创建带有草图斜面的几何体的类。草图斜面是一种在零件设计中常见的特征&#xff0c;它可以在零件的表面上创建一个倾斜的面&#xff0c;通常用于便于零件的脱模或是增加零件的强度。 本例演示了如何创建一个…

启动nginx时报错:signal process started

解决方案&#xff0c;直接使用该命令启动&#xff0c;指向nginx.conf配置文件&#xff1a; nginx -c /www/wdlinux/nginx/conf/nginx.conf 启动成功&#xff1a;

C语言高质量编程之assert()和const

目录 编程中常见的错误 assert() const 编程中常见的错误 在编程中我们通常会遇到三种错误形式&#xff0c;分别是&#xff1a;编译型错误&#xff0c;链接型错误&#xff0c;运行时错误。 编译型错误&#xff1a; 在编译阶段发生的错误&#xff0c;绝大多数情况是由语法错误…

全栈的自我修养 ———— react实现滑动验证

实现滑动验证 展示依赖实现不借助create-puzzle借助create-puzzle 展示 依赖 npm install rc-slider-captcha npm install create-puzzleapi地址 实现 不借助create-puzzle 需要准备两张图片一个是核验图形&#xff0c;一个是原图------> 这个方法小编试了后感觉比较麻烦…

初探vercel托管项目

文章目录 第一步、注册与登录第二步、本地部署 在个人网站部署的助手vercel&#xff0c;支持 Github部署&#xff0c;只需简单操作&#xff0c;即可发布&#xff0c;方便快捷&#xff01; 第一步、注册与登录 进入vercel【官网】&#xff0c;在右上角 login on&#xff0c;可登…

图解JDK 8 HashMap

HashMap-简介 HashMap 主要用来存放键值对&#xff0c;它基于哈希表的 Map 接口实现&#xff0c;是常用的 Java 集合之一&#xff0c;是非线程安全的。 HashMap 可以存储 null 的 key 和 value&#xff0c;但 null 作为键只能有一个&#xff0c;null 作为值可以有多个 JDK1.8…