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

LeetCode 算法:翻转二叉树 c++

原题链接🔗:翻转二叉树
难度:简单⭐️

题目

给你一棵二叉树的根节点 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 = []
输出:[]

提示

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

题解

递归法

  1. 解题思路: 翻转二叉树的解题思路主要基于递归和树的遍历。以下是详细的步骤和思路:

  2. 理解问题:首先,明确题目要求翻转二叉树,即将每个节点的左子树和右子树互换。

  3. 递归方法:递归是解决这个问题的自然选择,因为它可以很好地处理树结构的遍历。

  4. 递归终止条件:递归的基本终止条件是当节点为空时,不需要翻转,直接返回nullptr

  5. 递归逻辑

    • 在递归到每个节点时,首先交换当前节点的左子树和右子树。
    • 然后,递归地翻转当前节点的左子树(原来的右子树)。
    • 接着,递归地翻转当前节点的右子树(原来的左子树)。
  6. 递归返回值:在递归调用结束后,返回当前节点。虽然在翻转操作中,我们关心的是操作本身而不是返回值,但递归需要返回值来构建翻转后的树结构。

  7. 编写递归函数:实现递归函数,使用条件语句来处理递归终止条件,并使用递归调用来翻转子树。

  8. 测试:使用不同的二叉树结构来测试你的翻转算法,确保它可以正确地翻转所有类型的树。

  9. 优化:考虑算法的时间复杂度和空间复杂度。翻转操作的时间复杂度是O(n),其中n是树中的节点数,因为每个节点恰好被访问一次。空间复杂度是O(h),其中h是树的高度,这是因为递归调用的深度。

  10. 边界条件:确保处理了所有边界条件,如空树或只有一个节点的树。

  11. 代码实现:将上述思路转化为代码实现。

  1. 复杂度
  • 时间复杂度是 O(N),其中 N 为二叉树节点的数目。我们会遍历二叉树中的每一个节点,对每个节点而言,我们在常数时间内交换其两棵子树;
  • 空间复杂度是 O(N),使用的空间由递归栈的深度决定,它等于当前节点在二叉树中的高度。在平均情况下,二叉树的高度与节点个数为对数关系,即 O(log⁡N)。而在最坏情况下,树形成链状,空间复杂度为 O(N)。
  1. c++ demo
#include <iostream>
#include <queue>// 定义二叉树节点
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};// 翻转二叉树的解决方案
class Solution {
public:TreeNode* invertTree(TreeNode* root) {if (!root) return nullptr;  // 递归终止条件:如果节点为空,返回nullptrstd::swap(root->left, root->right);  // 交换当前节点的左右子树invertTree(root->left);             // 递归翻转左子树invertTree(root->right);            // 递归翻转右子树return root;                        // 返回翻转后的树的根节点}
};// 辅助函数:按层序遍历打印二叉树
void printLevelOrder(TreeNode* root) {if (!root) return;std::queue<TreeNode*> q;q.push(root);while (!q.empty()) {TreeNode* node = q.front();q.pop();if (node->left) q.push(node->left);if (node->right) q.push(node->right);std::cout << node->val << " ";}std::cout << std::endl;
}// 主函数
int main() {Solution solution;// 创建示例二叉树//       4//      / \//     2   7//    / \ / \//   1  3 6  9TreeNode* root = new TreeNode(4);root->left = new TreeNode(2);root->right = new TreeNode(7);root->left->left = new TreeNode(1);root->left->right = new TreeNode(3);root->right->left = new TreeNode(6);root->right->right = new TreeNode(9);std::cout << "Original binary tree:" << std::endl;printLevelOrder(root);// 翻转二叉树TreeNode* invertedRoot = solution.invertTree(root);std::cout << "Inverted binary tree:" << std::endl;printLevelOrder(invertedRoot);// 清理分配的内存delete root->left->left;delete root->left->right;delete root->left;delete root->right->left;delete root->right->right;delete root->right;delete root;return 0;
}
  • 输出结果:

Original binary tree:
4 2 7 1 3 6 9
Inverted binary tree:
4 7 2 9 6 3 1
在这里插入图片描述

相关文章:

LeetCode 算法:翻转二叉树 c++

原题链接&#x1f517;&#xff1a;翻转二叉树 难度&#xff1a;简单⭐️ 题目 给你一棵二叉树的根节点 root &#xff0c;翻转这棵二叉树&#xff0c;并返回其根节点。 示例 1&#xff1a; 输入&#xff1a;root [4,2,7,1,3,6,9] 输出&#xff1a;[4,7,2,9,6,3,1] 示例 …...

七天速通javaSE:第五天 数组进阶

文章目录 前言一、二维数组二、Arrays类1.toString打印数组内各元素1.1 示例1.2 自己实现内部逻辑 2. sort升序排列3. fill数组填充&#xff08;重新赋值&#xff09;4.equals比较数组元素是否相等 三、冒泡排序 前言 本文将学习二维数组、arrays类以及冒泡排序 一、二维数组 …...

游戏心理学Day28

独立游戏团队架构 独立游戏工作室是一个包括编程美术设计院校项目管理和运营等各种职能的团队找到可以共同奋斗。数月甚至数年的合适人选并不是一件容易的事情。游戏开发过程中要涉及多种常规工作。小团队的每个成员通常都要身兼数职&#xff0c;而且有些角色常由多人担任。 …...

鸿蒙开发设备管理:【@ohos.multimodalInput.inputEventClient (注入按键)】

注入按键 InputEventClient模块提供了注入按键能力。 说明&#xff1a; 本模块首批接口从API version 8开始支持。后续版本的新增接口&#xff0c;采用上角标单独标记接口的起始版本。本模块接口均为系统接口&#xff0c;三方应用不支持调用。 导入模块 import inputEventCli…...

C++:std::function的libc++实现

std::function是个有点神奇的模板&#xff0c;无论是普通函数、函数对象、lambda表达式还是std::bind的返回值&#xff08;以上统称为可调用对象&#xff08;Callable&#xff09;&#xff09;&#xff0c;无论可调用对象的实际类型是什么&#xff0c;无论是有状态的还是无状态…...

DM 的断点续传测试

作者&#xff1a; 大鱼海棠 原文来源&#xff1a; https://tidb.net/blog/4540ae34 一、概述 DM有all、full、incremental三种数据迁移同步方式&#xff08;task-mode&#xff09;&#xff0c;在all同步模式下&#xff0c;因一些特殊情况&#xff0c;需要变更上游MySQL的数…...

力扣每日一题 6/30 记忆化搜索/动态规划

博客主页&#xff1a;誓则盟约系列专栏&#xff1a;IT竞赛 专栏关注博主&#xff0c;后期持续更新系列文章如果有错误感谢请大家批评指出&#xff0c;及时修改感谢大家点赞&#x1f44d;收藏⭐评论✍ 494.目标和【中等】 题目&#xff1a; 给你一个非负整数数组 nums 和一个…...

图像基础知识入门【图像概念不同图像格式】

图像基础知识入门【图像概念&不同图像格式】 最近有在处理图像转换&#xff0c;因此稍微补足了一下图像相关知识&#xff0c;特在此记录。下面汇总是我根据自己理解和网上查阅资料而来。如有错误&#xff0c;欢迎大家指正。 1 基础概念 像素/分辨率 像素(Pixel)&#xff…...

HP服务器基于SNMP-ilo4的硬件监控指标解读

监控易是一款功能全面的IT基础设施监控软件&#xff0c;它通过SNMP协议与HP服务器内置的ilo4远程管理卡进行通信&#xff0c;实现对HP服务器硬件状态的实时监控。本文将针对监控易中基于SNMP-ilo4的HP服务器硬件监控指标进行解读&#xff0c;帮助运维团队更好地理解和应用这些监…...

Android13系统导航栏添加音量加减键按钮功能

不知道为什么拿到芯片原厂发布给我们的Android13系统源码编译后&#xff0c;导航栏没有音量加减键&#xff0c;客户有反馈这个问题&#xff0c;所以特意加了一下&#xff0c;修改记录如下&#xff1a;frameworks/base目录下 commit 9cb2244d61a237cab03c540bfcca6e4fac2bea2c …...

普及GIS知识,推动产业发展

915 GIS节&#xff1a;普及GIS知识&#xff0c;推动产业发展 自2008年起&#xff0c;每年的9月15日被定为“GIS节”&#xff0c;这一特殊的节日由超图首次发起倡议&#xff0c;旨在打造一个普及和传播GIS&#xff08;地理信息系统&#xff09;知识的平台&#xff0c;促进大众对…...

第2章-Python编程基础

#本章目标 1&#xff0c;了解什么是计算机程序 2&#xff0c;了解什么是编程语言 3&#xff0c;了解编程语言的分类 4&#xff0c;了解静态语言与脚本语言的区别 5&#xff0c;掌握IPO程序编写方法 6&#xff0c;熟练应用输出函数print与输入函数input 7&#xff0c;掌握Python…...

LDO产品的基础知识解析

低压降稳压器 (LDO)是一种用于调节较高电压输入产生的输出电压的简单方法。在大多数情况下&#xff0c;低压降稳压器都易于设计和使用。然而&#xff0c;如今的现代应用都包括各种各样的模拟和数字系统&#xff0c;而有些系统和工作条件将决定哪种LDO最适合相关电路&#xff0c…...

如何利用python画出AHP-SWOT的战略四边形(四象限图)

在企业或产业发展的相关论文分析中&#xff0c;常用到AHP-SWOT法进行定量分析&#xff0c;形成判断矩阵后&#xff0c;如何构造整洁的战略四边形是分析的最后一个环节&#xff0c;本文现将相关代码发布如下&#xff1a; import mpl_toolkits.axisartist as axisartist import …...

适用于智慧城市、智慧文旅等在线场景的轻量级3D数字人引擎MyAvatar简介

本人研发的国内首个纯面向web应用和小程序的轻量级3D虚拟人引擎MyAvatar。 功能简述 支持3D模型定制&#xff08;写实或卡通风格均可&#xff0c;人物模型需实现绑定和变形&#xff09;动画可以内置于模型中&#xff0c;也可以单独以glb或fbx格式导出并动态加载支持readyplay…...

Excel显示/隐藏批注按钮为什么是灰色?

在excel中&#xff0c;经常使用批注来加强数据信息的提示&#xff0c;有时候会把很多的批注显示出来&#xff0c;但是再想将它们隐藏起来&#xff0c;全选工作表后&#xff0c;“显示/隐藏批注”按钮是灰色的&#xff0c;不可用。 二、可操作方法 批注在excel、WPS表格中都是按…...

ArtTS系统能力-通知的学习(3.1)

上篇回顾&#xff1a; ArtTS语言基础类库-容器类库内容的学习(2.10.2&#xff09; 本篇内容&#xff1a; ArtTS系统能力-通知的学习&#xff08;3.1&#xff09; 一、 知识储备 1. 基础类型通知 按内容分成四类&#xff1a; 类型描述NOTIFICATION_CONTENT_BASIC_TEXT普通文…...

Apollo9.0 PNC源码学习之Planning模块(三)—— public_road_planner

前面文章: (1)Apollo9.0 PNC源码学习之Planning模块(一)—— 规划概览 (2)Apollo9.0 PNC源码学习之Planning模块(二)—— planning_component 1 planning_interface_base 规划接口基类: planning\planning_interface_base\planner_base\planner.h #pragma once#in…...

【Elasticsearch】linux使用supervisor常驻Elasticsearch,centos6.10安装 supervisor

背景&#xff1a; linux服务器&#xff0c;CentOS 6操作系统&#xff0c;默认版本python2.6.6&#xff0c;避免安装过多的依赖不升级python 在网上查的资料python2.6.6兼容supervisor版本 3.1.3 安装supervisor 手动在python官网下载supervisor&#xff0c;并上传到服务器 下…...

推荐系统三十六式学习笔记:原理篇.模型融合14|一网打尽协同过滤、矩阵分解和线性模型

目录 从特征组合说起FM模型1.原理2.模型训练3.预测阶段4.一网打尽其他模型5.FFM 总结 在上一篇文章中&#xff0c;我们讲到了使用逻辑回归和梯度提升决策树组合的模型融合办法&#xff0c;用于CTR预估&#xff0c;给这个组合起了个名字&#xff0c;叫“辑度组合”。这对组合中&…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

三维GIS开发cesium智慧地铁教程(5)Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。

1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj&#xff0c;再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...

NPOI操作EXCEL文件 ——CAD C# 二次开发

缺点:dll.版本容易加载错误。CAD加载插件时&#xff0c;没有加载所有类库。插件运行过程中用到某个类库&#xff0c;会从CAD的安装目录找&#xff0c;找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库&#xff0c;就用插件程序加载进…...

FFmpeg:Windows系统小白安装及其使用

一、安装 1.访问官网 Download FFmpeg 2.点击版本目录 3.选择版本点击安装 注意这里选择的是【release buids】&#xff0c;注意左上角标题 例如我安装在目录 F:\FFmpeg 4.解压 5.添加环境变量 把你解压后的bin目录&#xff08;即exe所在文件夹&#xff09;加入系统变量…...

Rust 开发环境搭建

环境搭建 1、开发工具RustRover 或者vs code 2、Cygwin64 安装 https://cygwin.com/install.html 在工具终端执行&#xff1a; rustup toolchain install stable-x86_64-pc-windows-gnu rustup default stable-x86_64-pc-windows-gnu ​ 2、Hello World fn main() { println…...

c# 局部函数 定义、功能与示例

C# 局部函数&#xff1a;定义、功能与示例 1. 定义与功能 局部函数&#xff08;Local Function&#xff09;是嵌套在另一个方法内部的私有方法&#xff0c;仅在包含它的方法内可见。 • 作用&#xff1a;封装仅用于当前方法的逻辑&#xff0c;避免污染类作用域&#xff0c;提升…...

深度解析:etcd 在 Milvus 向量数据库中的关键作用

目录 &#x1f680; 深度解析&#xff1a;etcd 在 Milvus 向量数据库中的关键作用 &#x1f4a1; 什么是 etcd&#xff1f; &#x1f9e0; Milvus 架构简介 &#x1f4e6; etcd 在 Milvus 中的核心作用 &#x1f527; 实际工作流程示意 ⚠️ 如果 etcd 出现问题会怎样&am…...