学习记录:js算法(四十三):翻转二叉树

文章目录

    • 翻转二叉树
      • 我的思路
      • 网上思路
        • 递归
    • 总结

翻转二叉树

给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点

图一:
在这里插入图片描述

图二:
在这里插入图片描述

示例 1:(如图一)
输入:root = [4,2,7,1,3,6,9]
输出:[4,7,2,9,6,3,1]示例 2:(如图二)
输入:root = [2,1,3]
输出:[2,3,1]示例 3:
输入:root = []
输出:[]

我的思路
循环
网上思路
递归、栈

我的思路

var invertTree = function (root) {if (!root) return null;const queue = [root];while (queue.length > 0) {const current = queue.shift();[current.left, current.right] = [current.right, current.left];if (current.left) queue.push(current.left);if (current.right) queue.push(current.right);}return root;
};

讲解

  1. 首先检查根节点是否为空,如果为空,直接返回 null
  2. 使用一个数组 nodes 来存储待处理的节点,初始化时将根节点放入数组。
  3. 使用 for 循环遍历数组中的节点:
    • 取出当前节点 current
    • 交换当前节点的左右子树。
    • 如果当前节点的左子节点不为空,将其加入数组;如果右子节点不为空,也加入数组。
  4. 当所有节点处理完毕后,返回翻转后的根节点。

网上思路

递归
var invertTree = function (root) {if (!root) return null; // 如果树为空,直接返回 null// 递归翻转左右子树const left = invertTree(root.left);const right = invertTree(root.right);// 交换左右子树root.left = right;root.right = left;return root; // 返回翻转后的根节点
}

讲解

  1. 基线条件:首先检查当前节点 root 是否为空。如果是,直接返回 null
  2. 递归调用:
    • 使用 invertTree(root.left) 递归翻转左子树,并将结果存储在 left 变量中。
    • 使用 invertTree(root.right) 递归翻转右子树,并将结果存储在 right 变量中。
  3. 交换左右子树:将当前节点的左子树设置为 right,右子树设置为 left
  4. 返回根节点:返回当前节点 root,以便在更高层的递归中继续处理。
var invertTree = function (root) {if (!root) return null; // 如果树为空,直接返回 nullconst stack = [root]; // 使用栈来存储节点while (stack.length > 0) {const current = stack.pop(); // 取出栈顶的节点// 交换当前节点的左右子树[current.left, current.right] = [current.right, current.left];// 将非空的左右子节点加入栈if (current.left) stack.push(current.left);if (current.right) stack.push(current.right);}return root; // 返回翻转后的根节点
}

详解

  1. 基线条件:首先检查根节点 root 是否为空。如果是,直接返回 null。
  2. 栈初始化:使用一个数组 stack 来模拟栈,初始化时将根节点放入栈。
  3. 循环处理:
    • 当栈不为空时,弹出栈顶节点 current
    • 交换当前节点的左右子树。
    • 如果当前节点的左子节点不为空,将其压入栈;如果右子节点不为空,也压入栈。
  4. 返回根节点:返回当前节点 root,即翻转后的树的根节点。

总结

解法挺多的,但是核心是一样的

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

Python记录

1.冒泡排序 时间复杂度O(n^2) 选择、插入都是 def bubble(data, reverse):for i in range(len(data)-1):for j in range(len(data)-i-1):if data[j] > data[j1]:data[j], data[j1] data[j1], data[j]if reverse:data.reverse()return data 2.快速排序 时间…

护理陪护小程序|陪护系统||陪护系统开发

在当今社会,随着人口老龄化的加剧和家庭结构的变化,护理与陪护服务的需求日益增长。为了更好地满足这一市场需求,并提升服务效率与质量,护理陪护小程序应运而生。这类小程序不仅为用户提供了便捷、高效的服务预约与管理平台&#…

828华为云征文 | 云服务器Flexus X实例,Docker集成搭建Redis集群

828华为云征文 | 云服务器Flexus X实例,Docker集成搭建Redis集群 Redis 集群是一种分布式的 Redis 解决方案,能够在多个节点之间分片存储数据,实现水平扩展和高可用性。与传统的主从架构不同,Redis 集群支持数据自动分片、主节点故…

J Transl Med结肠癌分子分型+简单实验

目录 技术路线 实验设计(药物敏感性) 亮点 方法 从 TCGA 和 GEO 数据库下载大量和单细胞 RNA 测序以及 CRC 的临床数据。HRGs 和 LMRGs 来自分子特征数据库。使用 R 软件包 DESeq2 进行差异表达分析。使用无监督聚类进行分子亚型。使用单变量 Cox 回…

嘉宾云集旌城 只为大赛而来 2024ISGC国际烈酒(中国)大奖赛在德阳落下帷幕

秋高气爽、古蜀之源,迎来第六届国际烈酒(中国)大奖赛;五谷丰登、重装之都,齐聚百名国际烈酒大奖赛评委。 9月18日,由德阳市人民政府、国家葡萄酒及白酒露酒产品质量检验检测中心、上海合作组织多功能经贸平…

图片压缩怎么弄?教你5种图片压缩小技巧

现如今,图片已成为我们日常生活和工作不可或缺的一部分。然而,高清图片往往伴随着庞大的文件体积,给存储和传输带来诸多不便。这时候我们就需要对图片进行适当的压缩处理,那么该怎么做呢?下面教大家5种图片压缩小技巧&…

GBase 8s 安装手册

没有失败,只有暂时停止成功! 一:简介 GBase 8s 产品支持多种处理器平台,除国际主流的 x86_64 处理器(包括 Intel 和 AMD) 外,全面支持飞腾、鲲鹏、龙芯、兆芯、海光、申威等国产处理器。 GBas…

2025秋招内推|招联金融

【投递方式】 直接扫下方二维码,使用内推码: igcefb 【招聘岗位】 深圳,武汉: 后台开发 前端开发 数据开发 数据运营 算法开发 技术运维 软件测试 产品策划 产品运营 客户体验管理 风险管理 资产管理 【校招流程】 简历投递:9月…

kafka 消费者线程安全问题详细探讨

内容概要 主要内容 常见错误案例 下面这段代码大概逻辑 初始化时 实例化KafkaConsumer, 开启线程拉取消息并且处理 资源释放回调 停止线程、调用kafkaConsumer.close进行资源释放 表面上没有问题,但实际上可能出现线程安全问题,因为poll 和 close 两…

Jetpack Compose 核心组件(Text, Images, Buttons)(6)

导读大纲 1.1 基本组件介绍1.2 Text1.2.1 基本用法1.2.2 设计文字风格 1.3 Image组件1.3.1 从各种来源加载图片1.3.2 关键属性1.3.3 如何加载和显示不同类型的图像1.3.4 内容描述和无障碍访问: 1.4 Button组件1.4.1 基本用法1.4.2 装饰和自定义1.4.3 处理按钮点击1.4.4 重要考虑…

基于python深度学习遥感影像地物分类与目标识别、分割实践技术

我国高分辨率对地观测系统重大专项已全面启动,高空间、高光谱、高时间分辨率和宽地面覆盖于一体的全球天空地一体化立体对地观测网逐步形成,将成为保障国家安全的基础性和战略性资源。未来10年全球每天获取的观测数据将超过10PB,遥感大数据时…

JS惰性函数两种实现方式

惰性函数的本质就是函数重写,所谓惰性载入,指函数执行的分支只会发生一次。那什么时函数重写呢?由于一个函数可以返回另一个函数,因此可以用新的函数在覆盖旧的函数。 惰性函数有两种实现方式: 1、在函数被调用时&am…

案例研究丨国控星鲨利用DataEase释放数据潜能,重塑业务视野

国药控股星鲨制药(厦门)有限公司(以下简称为国控星鲨)始创于1952年,前身为厦门鱼肝油厂,距今已经有70余年历史,是国家商务部认定的“中华老字号”企业。2011年,国药控股与厦门轻工集…

2024年国庆小长假即将来临,陪猫咪的同时应该如何清浮毛

在父母眼中我们是不是永远都长不大?每次和他们讨论一点事情就开始吵起来。这不,前两天想着和好久不见的朋友去见面,出门前还要被逼问一番。 去到朋友家,发现朋友养了两只可爱的小猫,一时心动上头,我也转身…

通信工程学习:什么是MANO管理编排

MANO:管理编排 MANO:Management and Network Orchestration(管理和网络编排)在网络功能虚拟化(NFV)架构中扮演着至关重要的角色。MANO是一个由多个功能实体组合而成的层次,这些功能实体负责管理…

地图定位流程

用户端在小程序认证通过后会自动进行定位,也可以在首页手动定位,定位成功后用户在查询家政服务项目时会根据定位的城市查询该城市有哪些服务项目。 高德地图配置 小程序端的定位是通过手机的定位模块进行定位,定位成功获取经纬度坐标&#x…

吸烟行为检测、重点区域吸烟检测、吸烟检测算法样本标注

吸烟检测算法主要用于公共场所、工作场所和家庭环境中的吸烟行为监控,通过图像识别技术来检测和识别吸烟行为,以确保环境卫生和公共安全。这种技术可以帮助管理者实时监控吸烟行为,及时采取措施,减少二手烟的危害。 一、技术实现…

55 循环神经网络RNN的实现_by《李沐:动手学深度学习v2》pytorch版

系列文章目录 文章目录 系列文章目录循环神经网络的从零开始实现[**独热编码**]初始化模型参数循环神经网络模型预测[**梯度裁剪**]训练小结练习 循环神经网络的从零开始实现 import math import torch from torch import nn from torch.nn import functional as F from d2l i…

大数据系统调优:从DAG到单机

目标:优化T10的时效性全局DAG调度层优化:提前任务开始时间: 1. 优化慢结点:T10依赖了T4,T7,T8, 其中T8为瓶颈,如果T8能提前点完成,T10可以早点开始,就能早点完成 2. 快结点做更多预计算…

WEB领域是不是黄了还是没黄

进入2024年后,WEB领域大批老表失业,一片哀嚎,个个饿的鬼叫狼嚎,为啥呢,下面是我个人的见解和看法。 中国程序员在应用层的集中 市场需求:中国的互联网行业在过去几年中经历了爆炸性增长,尤其是…