数据结构与算法之二叉树: LeetCode 226. 翻转二叉树 (Typescript版)
翻转二叉树
- https://leetcode.cn/problems/invert-binary-tree/
描述
- 给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。
示例 1
4 4/ \ / \2 7 ===> 7 2/ \ / \ / \ / \1 3 6 9 9 6 3 1
输入:root = [4,2,7,1,3,6,9]
输出:[4,7,2,9,6,3,1]
示例 2
2 2/ \ ===> / \1 3 3 1
输入:root = [2,1,3]
输出:[2,3,1]
示例 3
输入:root = []
输出:[]
提示
- 树中节点数目范围在 [0, 100] 内
- -100 <= Node.val <= 100
算法实现
1 )深度优先递归版本
/*** Definition for a binary tree node.* class TreeNode {* val: number* left: TreeNode | null* right: TreeNode | null* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {* this.val = (val===undefined ? 0 : val)* this.left = (left===undefined ? null : left)* this.right = (right===undefined ? null : right)* }* }*/function invertTree(root: TreeNode | null): TreeNode | null {// 如果是叶子节点,没有左右子树,这里为null, 则停止if(!root) return null;// 将翻转树返回return {val: root.val,left: invertTree(root.right),right: invertTree(root.left)}
}
- 解题思路
- 先翻转左右子树,再将子树换个位置
- 符合:分、解、合 特性
- 解题步骤
- 分:获取左右子树
- 解:递归地翻转左右子树
- 合:将翻转后的左右子树换个位置放到根节点
- 时间复杂度:O(n)
- 空间复杂度:需要存放 O(h) 个函数调用(h是树的高度),所以是 O(h)
2 )广度优先迭代实现
function invertTree(root: TreeNode | null): TreeNode | null {if (!root) return null;const queue: (TreeNode | null)[] = [root]; // 队列while(queue.length) {const qTop = queue.shift(); // 取出队首[qTop.left, qTop.right] = [qTop.right, qTop.left]; // 交换左右节点 (关键)if (qTop.left) queue.push(qTop.left); // 左孩子入队if (qTop.right) queue.push(qTop.right); // 右孩子入队}return root;
}
- 使用广度优先遍历处理
- 时间复杂度:O(n)
- 空间复杂度:O(n)
相关文章:
数据结构与算法之二叉树: LeetCode 226. 翻转二叉树 (Typescript版)
翻转二叉树 https://leetcode.cn/problems/invert-binary-tree/ 描述 给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。 示例 1 4 4/ \ / \2 7 >…...
lightdb-ignore_row_on_dupkey_index
LightDB 支持 ignore_row_on_dupkey_index hint LightDB 从23.4 开始支持oracle的 ignore_row_on_dupkey_index hint, 这个hint是用来忽略唯一键冲突的。类似与mysql的 insert ignore。 语法如下: 在LightDB中ignore_row_on_dupkey_index的效果等同于o…...
wangeditor实时预览
<template><div><!--挂载富文本编辑器--><div style"width: 45%;float: left;margin-left: 2%"><p>编辑内容</p><div id"editor" style"height: 100%"></div></div><div style"w…...
【前沿技术了解】web图形Canvas、svg、WebGL、数据可视化引擎的技术选型
目录 Canvas:HTML5新增 Canvas标签(画布) 渲染上下文canvas.getContext(contextType[, contextAttributes]) 上下文类型(contextType) 上下文属性 (contextAttributes) 示例 动画 setInterval(function, delay)…...
【Java】循环语句练习
文章目录 1. 计算5的阶乘2. 计算 1! 2! 3! 4! 5!3. 数字9 出现的次数4. 判定素数5. 求1-100之间的素数6. 求2个整数的最大公约数7. 计算分数的值8. 模拟登陆9. 输出乘法口诀表10. 求出0~999之间的所有“水仙花数”并输出11. 猜数字游戏🙈 1. 计算5的…...
「Verilog学习笔记」非整数倍数据位宽转换24to128
专栏前言 本专栏的内容主要是记录本人学习Verilog过程中的一些知识点,刷题网站用的是牛客网 要实现24bit数据至128bit数据的位宽转换,必须要用寄存器将先到达的数据进行缓存。24bit数据至128bit数据,相当于5个输入数据第6个输入数据的拼接成一…...
2023亚太地区数学建模C题思路模型代码论文
C题的参考思路: 1,问题1的思路: 确定研究问题的主要指标体系(新能源电车的售出数量、安全性指标、充电桩数目、电池续 航里程等),收集指标的对应数据,检验数据是否服从正态性: 若服从正态分布: 0,可考虑优先采用“多元方差分析”模…...
苹果商城App上架指南在中发里查看
苹果商城App上架指引可以在app应用分发平台网站上查看。具体步骤如下: 登录苹果开发者网站。进入“Certificates, Identifiers & Profiles”选项。在页面左侧选择“App Store Connect”。点击“App Store Connect”页面顶部的“Developer Guide”。在左侧菜单中…...
Android 框架层AIDL 添加接口
文章目录 AIDL的原理构建AIDL的流程往冻结的AIDL中加接口 AIDL的原理 可以利用ALDL定义客户端与服务均认可的编程接口,以便二者使用进程间通信 (IPC) 进行相互通信。在 Android 中,一个进程通常无法访问另一个进程的内存。因此,为进行通信&a…...
ubuntu命令行下中文乱码怎么解决
大家好,今天来介绍ubuntu命令行中文乱码怎么解决(ubuntu中文文件名乱码)的问题,以下是渲大师小编对此问题的归纳和整理,感兴趣的来一起看看吧! ubuntu命令行下中文乱码怎么解决 我也呀见过这个问题 一. Ubuntu默认的中文字符编码 Ubuntu默认的中文字谈码符编码为zh_CN.UT…...
沈阳陪诊系统|陪诊软件开发功能
陪诊小程序的出现它可以帮助患者或家属解决就医过程中的各种问题。根据数据显示,2021年中国陪诊市场规模约为36.7亿元,预计到2025年将达到100亿元。同时,在医疗行业数字化转型的大背景下,陪诊微信小程序作为一种创新的医疗服务模式…...
Element-Plus 表格 el-table 如何支持分页多选
🚀 作者主页: 有来技术 🔥 开源项目: youlai-mall 🍃 vue3-element-admin 🍃 youlai-boot 🌺 仓库主页: Gitee 💫 Github 💫 GitCode 💖 欢迎点赞…...
网站被流量攻击了,该怎么处理
几乎每个网站都面临被攻击或者入侵的风险,无论是简单的博客论坛、投资平台、小型的独立电商网站还是动态电子商务平台都有被攻击的情况出现,只是或大或小,或多或少罢了 为什么网站会被攻击?黑客如何来入侵这些网站?如何才能有效保护我的网站不…...
配置特定 IP 地址走指定网关
公司有两个日常上网用的路由器,分别接不同的两条网线,虽然都是电信的,但是一条偶尔会抽风,我的 VPS 会连不上,也就是挂在上面的 SS 无法使用。恰好这根线是公司接台式机的,也就是说平时上班偶尔会无法科学上…...
Linux的基本指令(四)
目录 前言 时间相关的指令 date指令 时间戳 日志 时间戳转化为具体的时间 cal指令 find指令(十分重要) grep指令(行文本过滤工具) 学前补充 什么是打包和压缩? 为什么要打包和压缩? 怎么打包和…...
vue+elementui如何实现在表格中点击按钮预览图片?
效果图如上: 使用el-image-viewer 重点 : 引入 import ElImageViewer from "element-ui/packages/image/src/image-viewer"; <template><div class"preview-table"><el-table border :data"tableData" …...
LLaMA 2:开源的预训练和微调语言模型推理引擎 | 开源日报 No.86
facebookresearch/llama Stars: 36.0k License: NOASSERTION LLaMA 2 是一个开源项目,用于加载 LLaMA 模型并进行推理。 该项目的主要功能是提供预训练和微调后的 LLaMA 语言模型的权重和起始代码。这些模型参数范围从 7B 到 70B 不等。 以下是该项目的关键特性…...
01-AI大模型智能客服 V0.1「上」
你好,我是悦创。 首发:https://mp.weixin.qq.com/s/6MTkpWZCEbFWOcUn0Vexvw V0.1 版本我将分为上中下三篇进行书写和发布,欢迎分享和我微信进讨论群:Jiabcdefh。 计划: 会迭代好几个版本,看阅读量和点赞…...
【23真题】罕见211!数一配英二!
今天分享的是23年合肥工业大学833的信号与系统数字信号处理试题及解析。合工大833考数一英二,这样的搭配还是很少见的。 本套试卷难度分析:22年合肥工业大学833考研真题,我也发布过,若有需要,戳这里自取!平均分为80和…...
Linux 项目自动化构建工具:make/makefile
什么是 make make 是一个命令,他会在源文件的当前目录下寻找 makefile 或者 Makefile 文件执行这个文件中的代码。 makefile 文件的编写 我们先来见见猪跑,看看 make 怎么用的: 下面是 makefile 文件的内容: 这是 test.c 中的…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...
【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力
引言: 在人工智能快速发展的浪潮中,快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型(LLM)。该模型代表着该领域的重大突破,通过独特方式融合思考与非思考…...
C# SqlSugar:依赖注入与仓储模式实践
C# SqlSugar:依赖注入与仓储模式实践 在 C# 的应用开发中,数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护,许多开发者会选择成熟的 ORM(对象关系映射)框架,SqlSugar 就是其中备受…...
在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?
uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件,用于在原生应用中加载 HTML 页面: 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...
基于TurtleBot3在Gazebo地图实现机器人远程控制
1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...
人机融合智能 | “人智交互”跨学科新领域
本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...
Java数值运算常见陷阱与规避方法
整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...
快刀集(1): 一刀斩断视频片头广告
一刀流:用一个简单脚本,秒杀视频片头广告,还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农,平时写代码之余看看电影、补补片,是再正常不过的事。 电影嘛,要沉浸,…...
从物理机到云原生:全面解析计算虚拟化技术的演进与应用
前言:我的虚拟化技术探索之旅 我最早接触"虚拟机"的概念是从Java开始的——JVM(Java Virtual Machine)让"一次编写,到处运行"成为可能。这个软件层面的虚拟化让我着迷,但直到后来接触VMware和Doc…...
flow_controllers
关键点: 流控制器类型: 同步(Sync):发布操作会阻塞,直到数据被确认发送。异步(Async):发布操作非阻塞,数据发送由后台线程处理。纯同步(PureSync…...
