当前位置: 首页 > news >正文

数据结构与算法之二叉树: 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 &#xff0c;翻转这棵二叉树&#xff0c;并返回其根节点。 示例 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&#xff0c; 这个hint是用来忽略唯一键冲突的。类似与mysql的 insert ignore。 语法如下&#xff1a; 在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&#xff1a;HTML5新增 Canvas标签&#xff08;画布&#xff09; 渲染上下文canvas.getContext(contextType[, contextAttributes]) 上下文类型&#xff08;contextType&#xff09; 上下文属性 (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&#xff5e;999之间的所有“水仙花数”并输出11. 猜数字游戏&#x1f648; 1. 计算5的…...

「Verilog学习笔记」非整数倍数据位宽转换24to128

专栏前言 本专栏的内容主要是记录本人学习Verilog过程中的一些知识点&#xff0c;刷题网站用的是牛客网 要实现24bit数据至128bit数据的位宽转换&#xff0c;必须要用寄存器将先到达的数据进行缓存。24bit数据至128bit数据&#xff0c;相当于5个输入数据第6个输入数据的拼接成一…...

2023亚太地区数学建模C题思路模型代码论文

C题的参考思路: 1&#xff0c;问题1的思路: 确定研究问题的主要指标体系(新能源电车的售出数量、安全性指标、充电桩数目、电池续 航里程等)&#xff0c;收集指标的对应数据&#xff0c;检验数据是否服从正态性: 若服从正态分布: 0&#xff0c;可考虑优先采用“多元方差分析”模…...

苹果商城App上架指南在中发里查看

苹果商城App上架指引可以在app应用分发平台网站上查看。具体步骤如下&#xff1a; 登录苹果开发者网站。进入“Certificates, Identifiers & Profiles”选项。在页面左侧选择“App Store Connect”。点击“App Store Connect”页面顶部的“Developer Guide”。在左侧菜单中…...

Android 框架层AIDL 添加接口

文章目录 AIDL的原理构建AIDL的流程往冻结的AIDL中加接口 AIDL的原理 可以利用ALDL定义客户端与服务均认可的编程接口&#xff0c;以便二者使用进程间通信 (IPC) 进行相互通信。在 Android 中&#xff0c;一个进程通常无法访问另一个进程的内存。因此&#xff0c;为进行通信&a…...

ubuntu命令行下中文乱码怎么解决

大家好,今天来介绍ubuntu命令行中文乱码怎么解决(ubuntu中文文件名乱码)的问题,以下是渲大师小编对此问题的归纳和整理,感兴趣的来一起看看吧! ubuntu命令行下中文乱码怎么解决 我也呀见过这个问题 一. Ubuntu默认的中文字符编码 Ubuntu默认的中文字谈码符编码为zh_CN.UT…...

沈阳陪诊系统|陪诊软件开发功能

陪诊小程序的出现它可以帮助患者或家属解决就医过程中的各种问题。根据数据显示&#xff0c;2021年中国陪诊市场规模约为36.7亿元&#xff0c;预计到2025年将达到100亿元。同时&#xff0c;在医疗行业数字化转型的大背景下&#xff0c;陪诊微信小程序作为一种创新的医疗服务模式…...

Element-Plus 表格 el-table 如何支持分页多选

&#x1f680; 作者主页&#xff1a; 有来技术 &#x1f525; 开源项目&#xff1a; youlai-mall &#x1f343; vue3-element-admin &#x1f343; youlai-boot &#x1f33a; 仓库主页&#xff1a; Gitee &#x1f4ab; Github &#x1f4ab; GitCode &#x1f496; 欢迎点赞…...

网站被流量攻击了,该怎么处理

几乎每个网站都面临被攻击或者入侵的风险&#xff0c;无论是简单的博客论坛、投资平台、小型的独立电商网站还是动态电子商务平台都有被攻击的情况出现,只是或大或小,或多或少罢了 为什么网站会被攻击&#xff1f;黑客如何来入侵这些网站&#xff1f;如何才能有效保护我的网站不…...

配置特定 IP 地址走指定网关

公司有两个日常上网用的路由器&#xff0c;分别接不同的两条网线&#xff0c;虽然都是电信的&#xff0c;但是一条偶尔会抽风&#xff0c;我的 VPS 会连不上&#xff0c;也就是挂在上面的 SS 无法使用。恰好这根线是公司接台式机的&#xff0c;也就是说平时上班偶尔会无法科学上…...

Linux的基本指令(四)

目录 前言 时间相关的指令 date指令 时间戳 日志 时间戳转化为具体的时间 cal指令 find指令&#xff08;十分重要&#xff09; grep指令&#xff08;行文本过滤工具&#xff09; 学前补充 什么是打包和压缩&#xff1f; 为什么要打包和压缩&#xff1f; 怎么打包和…...

vue+elementui如何实现在表格中点击按钮预览图片?

效果图如上&#xff1a; 使用el-image-viewer 重点 &#xff1a; 引入 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 是一个开源项目&#xff0c;用于加载 LLaMA 模型并进行推理。 该项目的主要功能是提供预训练和微调后的 LLaMA 语言模型的权重和起始代码。这些模型参数范围从 7B 到 70B 不等。 以下是该项目的关键特性…...

01-AI大模型智能客服 V0.1「上」

你好&#xff0c;我是悦创。 首发&#xff1a;https://mp.weixin.qq.com/s/6MTkpWZCEbFWOcUn0Vexvw V0.1 版本我将分为上中下三篇进行书写和发布&#xff0c;欢迎分享和我微信进讨论群&#xff1a;Jiabcdefh。 计划&#xff1a; 会迭代好几个版本&#xff0c;看阅读量和点赞…...

【23真题】罕见211!数一配英二!

今天分享的是23年合肥工业大学833的信号与系统数字信号处理试题及解析。合工大833考数一英二&#xff0c;这样的搭配还是很少见的。 本套试卷难度分析&#xff1a;22年合肥工业大学833考研真题&#xff0c;我也发布过&#xff0c;若有需要&#xff0c;戳这里自取!平均分为80和…...

Linux 项目自动化构建工具:make/makefile

什么是 make make 是一个命令&#xff0c;他会在源文件的当前目录下寻找 makefile 或者 Makefile 文件执行这个文件中的代码。 makefile 文件的编写 我们先来见见猪跑&#xff0c;看看 make 怎么用的&#xff1a; 下面是 makefile 文件的内容&#xff1a; 这是 test.c 中的…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端

&#x1f31f; 什么是 MCP&#xff1f; 模型控制协议 (MCP) 是一种创新的协议&#xff0c;旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议&#xff0c;它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

pam_env.so模块配置解析

在PAM&#xff08;Pluggable Authentication Modules&#xff09;配置中&#xff0c; /etc/pam.d/su 文件相关配置含义如下&#xff1a; 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块&#xff0c;负责验证用户身份&am…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...

佰力博科技与您探讨热释电测量的几种方法

热释电的测量主要涉及热释电系数的测定&#xff0c;这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中&#xff0c;积分电荷法最为常用&#xff0c;其原理是通过测量在电容器上积累的热释电电荷&#xff0c;从而确定热释电系数…...

【VLNs篇】07:NavRL—在动态环境中学习安全飞行

项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战&#xff0c;克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...

基于Java+MySQL实现(GUI)客户管理系统

客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息&#xff0c;对客户进行统一管理&#xff0c;可以把所有客户信息录入系统&#xff0c;进行维护和统计功能。可通过文件的方式保存相关录入数据&#xff0c;对…...

C#中的CLR属性、依赖属性与附加属性

CLR属性的主要特征 封装性&#xff1a; 隐藏字段的实现细节 提供对字段的受控访问 访问控制&#xff1a; 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性&#xff1a; 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑&#xff1a; 可以…...

使用LangGraph和LangSmith构建多智能体人工智能系统

现在&#xff0c;通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战&#xff0c;比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...