LeetCode 226.翻转二叉树（全网最多的解法）

LeetCode 226.翻转二叉树

1、题目

题目链接：226. 翻转二叉树
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：
image.png

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

示例 2：
image.png

输入：root = [2,1,3]
输出：[2,3,1]

示例 3：

输入：root = []
输出：[]

提示：

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

2、递归（前序遍历）

思路

我们从根节点开始翻转，先交换左右孩子节点，然后翻转左子树，最后翻转右子树。即可完成以 root 为根节点的整棵子树的翻转。

代码

#include <iostream>

using namespace std;

//Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {

public:
    TreeNode* invertTree(TreeNode* root) {
        // 如果根节点为空，则返回空指针
        if (root == nullptr) {
            return nullptr;
        }

        // 交换左右子树
        swap(root->left, root->right);

        // 递归翻转左子树
        invertTree(root->left);

        // 递归翻转右子树
        invertTree(root->right);

        // 返回翻转后的根节点
        return root;
    }
};

int main() {
    TreeNode* root = new TreeNode(4, new TreeNode(2, new TreeNode(1), new TreeNode(3)), new TreeNode(7, new TreeNode(6), new TreeNode(9)));
    Solution s;
    TreeNode* res = s.invertTree(root);
    cout << res->val << endl;
    cout << res->left->val << endl;
    cout << res->right->val << endl;
    cout << res->left->left->val << endl;
    cout << res->left->right->val << endl;
    cout << res->right->left->val << endl;
    cout << res->right->right->val << endl;

    delete root;
    return 0;
}

复杂度分析

  • 时间复杂度：O(N)，其中 N 为二叉树节点的数目。我们会遍历二叉树中的每一个节点，对每个节点而言，我们在常数时间内交换其两棵子树。
  • 空间复杂度：O(N)。使用的空间由递归栈的深度决定，它等于当前节点在二叉树中的高度。在平均情况下，二叉树的高度与节点个数为对数关系，即 O(log⁡N)。而在最坏情况下，树形成链状，空间复杂度为 O(N)。

3、递归（中序遍历）

思路

注意：写中序遍历的时候，不能仅仅只是将前序遍历的代码顺序调整一下。
因为在“中序遍历”的时候，左右子树已经交换过了，因此原来写 invertTree(root.right); 的地方，应该写作 invertTree(root.left);。

代码

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        // 如果根节点为空，则返回空指针
        if (root == nullptr) {
            return nullptr;
        }
        
        // 递归翻转左子树
        invertTree(root->left);

        // 交换左右子树
        swap(root->left, root->right);
        
        // 递归翻转右子树
        invertTree(root->left);

        // 返回反转后的根节点
        return root;
    }
};

复杂度分析

  • 时间复杂度：O(N)，其中 N 为二叉树节点的数目。我们会遍历二叉树中的每一个节点，对每个节点而言，我们在常数时间内交换其两棵子树。
  • 空间复杂度：O(N)。使用的空间由递归栈的深度决定，它等于当前节点在二叉树中的高度。在平均情况下，二叉树的高度与节点个数为对数关系，即 O(log⁡N)。而在最坏情况下，树形成链状，空间复杂度为 O(N)。

4、递归（后序遍历）

思路

我们从根节点开始，递归地对树进行遍历，并从叶子节点先开始翻转。如果当前遍历到的节点 root 的左右两棵子树都已经翻转，那么我们只需要交换两棵子树的位置，即可完成以 root 为根节点的整棵子树的翻转。

代码

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        // 如果根节点为空，则返回空指针
        if (root == nullptr) {
            return nullptr;
        }
        
        // 递归翻转左子树
        invertTree(root->left);
        
        // 递归翻转右子树
        invertTree(root->right);

        // 交换左右子树
        swap(root->left, root->right);

        // 返回反转后的根节点
        return root;
    }
};

复杂度分析

  • 时间复杂度：O(N)，其中 N 为二叉树节点的数目。我们会遍历二叉树中的每一个节点，对每个节点而言，我们在常数时间内交换其两棵子树。
  • 空间复杂度：O(N)。使用的空间由递归栈的深度决定，它等于当前节点在二叉树中的高度。在平均情况下，二叉树的高度与节点个数为对数关系，即 O(log⁡N)。而在最坏情况下，树形成链状，空间复杂度为 O(N)。

5、迭代法（前序遍历）

代码

class Solution {
// 迭代法(前序遍历)：使用栈，先将根节点入栈，然后不断弹出栈顶节点，交换其左右子树，并将右子树、左子树入栈，直到栈为空
public:
    TreeNode* invertTree(TreeNode* root) {
        // 如果根节点为空，则直接返回空
        if (root == nullptr) return nullptr;
        // 创建一个栈，用于存储待处理的节点
        stack<TreeNode*> stk;
        // 将根节点入栈
        stk.push(root);
        // 当栈不为空时，循环处理栈中的节点
        while(!stk.empty()) {
            // 取出栈顶节点
            TreeNode* node = stk.top();
            // 将栈顶节点出栈
            stk.pop();
            // 交换当前节点的左右子树
            swap(node->left, node->right);
            // 如果当前节点的右子树不为空，则将右子树入栈
            if(node->right) stk.push(node->right);
            // 如果当前节点的左子树不为空，则将左子树入栈
            if(node->left) stk.push(node->left);
        }
        // 返回根节点
        return root;
    }
};

复杂度分析

  • 时间复杂度：O(N)，其中 N 为二叉树节点的数目。我们会遍历二叉树中的每一个节点，对每个节点而言，我们在常数时间内交换其两棵子树。
  • 空间复杂度：O(N)。使用的空间由递归栈的深度决定，它等于当前节点在二叉树中的高度。在平均情况下，二叉树的高度与节点个数为对数关系，即 O(log⁡N)。而在最坏情况下，树形成链状，空间复杂度为 O(N)。

6、迭代法（中序遍历）

代码

class Solution {
// 迭代法(中序遍历)：使用栈，先将根节点入栈，然后不断弹出栈顶节点，交换其左右子树，并将右子树、左子树入栈，直到栈为空

public:
    TreeNode* invertTree(TreeNode* root) {
        stack<TreeNode*> stk;
        if (root != nullptr) {
            stk.push(root);
        }

        while (!stk.empty()) {
            TreeNode* node = stk.top();
            if (node != nullptr) {
                stk.pop();

                // 将右子节点入栈
                if (node->right) {
                    stk.push(node->right);
                }

                // 将当前节点再次入栈，用于后续交换左右子节点
                stk.push(node);
                stk.push(nullptr);

                // 将左子节点入栈
                if (node->left) {
                    stk.push(node->left);
                }
            } else {
                stk.pop();

                // 取出需要交换的节点
                node = stk.top();
                stk.pop();

                // 交换左右子节点
                swap(node->left, node->right);
            }
        }
        return root;
    }
};

复杂度分析

  • 时间复杂度：O(N)，其中 N 为二叉树节点的数目。我们会遍历二叉树中的每一个节点，对每个节点而言，我们在常数时间内交换其两棵子树。
  • 空间复杂度：O(N)。使用的空间由递归栈的深度决定，它等于当前节点在二叉树中的高度。在平均情况下，二叉树的高度与节点个数为对数关系，即 O(log⁡N)。而在最坏情况下，树形成链状，空间复杂度为 O(N)。

7、迭代法（后序遍历）

代码

class Solution {
// 迭代法(后序遍历)：使用栈，先将根节点入栈，然后不断弹出栈顶节点，并将右子树、左子树入栈，交换其左右子树，直到栈为空
public:
    TreeNode* invertTree(TreeNode* root) {
        // 如果根节点为空，则直接返回空
        if (root == nullptr) return nullptr;
        // 创建一个栈，用于存储待处理的节点
        stack<TreeNode*> stk;
        // 将根节点入栈
        stk.push(root);
        // 当栈不为空时，循环处理栈中的节点
        while(!stk.empty()) {
            // 取出栈顶节点
            TreeNode* node = stk.top();
            // 将栈顶节点出栈
            stk.pop();
            // 如果当前节点的右子树不为空，则将右子树入栈
            if(node->right) stk.push(node->right);
            // 如果当前节点的左子树不为空，则将左子树入栈
            if(node->left) stk.push(node->left);
            // 交换当前节点的左右子树
            swap(node->left, node->right);
        }
        // 返回根节点
        return root;
    }
};

复杂度分析

  • 时间复杂度：O(N)，其中 N 为二叉树节点的数目。我们会遍历二叉树中的每一个节点，对每个节点而言，我们在常数时间内交换其两棵子树。
  • 空间复杂度：O(N)。使用的空间由递归栈的深度决定，它等于当前节点在二叉树中的高度。在平均情况下，二叉树的高度与节点个数为对数关系，即 O(log⁡N)。而在最坏情况下，树形成链状，空间复杂度为 O(N)。

8、层序遍历（广度优先遍历）

思路

层序遍历也可以把每个节点的左右孩子都翻转一遍，我们可以使用队列，将根节点入队列，然后不断弹出队列头节点，交换其左右子树，并将右子树、左子树入队列，直到队列为空。

代码

class Solution {
// 层序遍历：使用队列，将根节点入队列，然后不断弹出队列头节点，交换其左右子树，并将右子树、左子树入队列，直到队列为空
public:
    TreeNode* invertTree(TreeNode* root) {
        // 创建一个队列用于存储待处理的节点
        queue<TreeNode*> que;
        // 如果根节点不为空，则将其加入队列
        if (root != nullptr) que.push(root);
        // 当队列不为空时，循环处理队列中的节点
        while (!que.empty()) {
            // 记录当前队列的大小
            int size = que.size();
            // 遍历当前队列中的所有节点
            for (int i = 0; i < size; i++) {
                // 取出队列中的节点
                TreeNode* node = que.front();
                // 将节点从队列中移除
                que.pop();
                // 交换节点的左右子树
                swap(node->left, node->right);
                // 如果节点的左子树不为空，则将其加入队列
                if (node->left) que.push(node->left);
                // 如果节点的右子树不为空，则将其加入队列
                if (node->right) que.push(node->right);
            }
        }
        // 返回处理后的根节点
        return root;
    }
};

复杂度分析

  • 时间复杂度：O(N)，其中 N 为二叉树节点的数目。我们会遍历二叉树中的每一个节点，对每个节点而言，我们在常数时间内交换其两棵子树。
  • 空间复杂度：O(N)。使用的空间由递归栈的深度决定，它等于当前节点在二叉树中的高度。在平均情况下，二叉树的高度与节点个数为对数关系，即 O(log⁡N)。而在最坏情况下，树形成链状，空间复杂度为 O(N)。

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

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

相关文章

Unity 性能优化之遮挡剔除（Occlusion Culling）（六）

Unity 性能优化之遮挡剔除（Occlusion Culling）（六）

提示&#xff1a;仅供参考&#xff0c;有误之处&#xff0c;麻烦大佬指出&#xff0c;不胜感激&#xff01; 文章目录 前言一、遮挡剔除是什么&#xff1f;二、静态遮挡剔除的使用步骤1.标记为遮挡剔除对象2.创建Occlusion Area组件3.烘焙4.Occlusion窗口Bake的参数Smallest Oc…
阅读更多...
MYSQL基础架构、执行过程分析、事务的实现、索引的选择、覆盖索引

MYSQL基础架构、执行过程分析、事务的实现、索引的选择、覆盖索引

本文是mysql45讲的1-5的总结 文章目录 基础架构连接器分析器优化器执行器SQL查询执行过程详细执行步骤 SQL更新执行过程重要的日志模块&#xff1a;redo log重要的日志模块&#xff1a;binlog阶段性提交 事务事务隔离的实现启动 索引数据库索引模型InnoDB索引组织结构主键选择…
阅读更多...
[Unity常见小问题]打包ios后无法修改模型透明度

[Unity常见小问题]打包ios后无法修改模型透明度

问题 在Editor下可以使用如下代码去修改模型的材质的透明度&#xff0c;但是打包ios后无法对透明度进行修改且没有任何warning和error using System.Collections; using System.Collections.Generic; using UnityEngine;public class NewBehaviourScript : MonoBehaviour {[R…
阅读更多...
订票系统|基于Springboot+vue的火车票订票系统(源码+数据库+文档)

订票系统|基于Springboot+vue的火车票订票系统(源码+数据库+文档)

订票系统目录 基于Springbootvue的火车票订票系统 一、前言 二、系统设计 三、系统功能设计 1会员信息管理 2 车次信息管理 3订票订单管理 4留言板管理 四、数据库设计 五、核心代码 六、论文参考 七、最新计算机毕设选题推荐 八、源码获取&#xff1a; 博主介绍…
阅读更多...
【RAG 论文】SKR：Self-Knowledge 指导下的 RAG

【RAG 论文】SKR：Self-Knowledge 指导下的 RAG

论文&#xff1a;Self-Knowledge Guided Retrieval Augmentation for Large Language Models ⭐⭐⭐⭐ Tsinghua, arXiv:2310.05002 文章目录 一、论文速读二、实现细节2.1 数据的收集2.2 引出 LLM 的 Self-Knowledge 的方法1&#xff09;Direct Prompting2&#xff09;In-Cont…
阅读更多...
正则将段落分割成句子

正则将段落分割成句子

这里分割段落不区分中英文标点&#xff0c;你可以根据需求改 分割后标点跟随句子后面 def split_sentences_keep_delimiter(text):pattern r[^。!&#xff01;?&#xff1f;:&#xff1a;;&#xff1b;,&#xff0c;][。!&#xff01;?&#xff1f;:&#xff1a;;&#xff…
阅读更多...
记录DemoApplication.java不变蓝问题

记录DemoApplication.java不变蓝问题

问题 解决方案 一、点击右下角加载 二、右键项目 勾选maven
阅读更多...
计算机毕设

计算机毕设

随着社会和国家的重视&#xff0c;大学对于大学生毕业设计越来越重视。 做软件设计设计方面&#xff0c;前后端分离是必不可少的&#xff0c;代码管理工具&#xff0c;前后端接口测试是项目中必须要用到的工具。做大数据设计方面&#xff0c;主要是要用到爬虫进行数据爬取&…
阅读更多...
多选择性更容易理解！基于可选择性遗传算法的微电网经济-低碳协调优化程序代码！

多选择性更容易理解！基于可选择性遗传算法的微电网经济-低碳协调优化程序代码！

前言 随着能源危机和环境污染日益严重&#xff0c;传的能源已不再满足人们日益增长的能源需求&#xff0c;丰富清洁的可再生能源是未来的发展方向&#xff0c;分布式可再生能源发电技术获得了飞速进步。然而&#xff0c;在引入分布式可再生电源后&#xff0c;微电网的复杂性以…
阅读更多...
音频智能切换器JR-AR42-A

音频智能切换器JR-AR42-A

憬锐JR-AR42-A音频自动智能切换器(四切一)&#xff0c;具备四路模拟卡侬立体声音频输入&#xff0c;两路模拟卡侬立体声音频输出&#xff0c;其中输入第1路和输出第1路为断电直通通道。具有输入音频信号幅度判别&#xff0c;可设置门限电平和切换延时时间&#xff0c;可以根据需…
阅读更多...
通信系列：通信中如何度量消息中所包含的信息量？如何评估通信系统的性能？

通信系列：通信中如何度量消息中所包含的信息量？如何评估通信系统的性能？

微信公众号上线&#xff0c;搜索公众号小灰灰的FPGA,关注可获取相关源码&#xff0c;定期更新有关FPGA的项目以及开源项目源码&#xff0c;包括但不限于各类检测芯片驱动、低速接口驱动、高速接口驱动、数据信号处理、图像处理以及AXI总线等 本节目录 一、通信中如何度量消息…
阅读更多...
代码随想录训练营31day-动态规划4

代码随想录训练营31day-动态规划4

一、完全背包&#xff08;参考博客&#xff09; 和01背包区别在于物品可以无限次放入背包。完全背包和01背包问题唯一不同的地方就是&#xff0c;每种物品有无限件。 因此在需要在遍历顺序上进行区别&#xff0c;参考代码随想录&#xff1a; 二、518.零钱兑换II 题目求的是组…
阅读更多...
ASP.NET网上图书预约系统的设计

ASP.NET网上图书预约系统的设计

摘 要 《网上图书预约系统的设计》是以为读者提供便利为前提而开发的一个信息管理系统&#xff0c;它不仅要求建立数据的一致性和完整性&#xff0c;而且还需要应用程序功能的完备、易用等特点。系统主要采用VB.NET作为前端的应用开发工具&#xff0c;利用SQL Server2000数据…
阅读更多...
初识指针（2）＜C语言＞

初识指针（2）＜C语言＞

前言 前文介绍完了一些指针基本概念&#xff0c;下面介绍一下&#xff0c;const关键字、指针的运算、野指针的成因以及避免&#xff0c;assert函数等。 目录 const&#xff08;常属性&#xff09; 变量的常属性 指针的常属性 指针的运算 ①指针 -整数 ②指针-指针 ③指针与…
阅读更多...
设计网页用什么软件

设计网页用什么软件

在设计网页时&#xff0c;可以使用多种软件来完成不同的任务。以下是一些常用的网页设计软件&#xff0c;以及它们的特点和用途。 1. Adobe Photoshop&#xff1a; Adobe Photoshop 是一款功能强大的图像编辑软件。在网页设计中&#xff0c;它常用于创建和编辑网页所需的图像、…
阅读更多...
Linux—-vim基础使用

Linux—-vim基础使用

1、基本概念 Vim的工作模式有四种&#xff0c;普通模式&#xff0c;输入模式&#xff0c;命令模式&#xff0c;可视模式。 在终端中打开vim&#xff0c;只需要输入vim 文件&#xff0c;在普通模式下按i就会进入到输入模式&#xff0c;按下:进入命令模式&#xff0c;输入:q就可…
阅读更多...
通义灵码：智能编码的革命性助手

通义灵码：智能编码的革命性助手

通义灵码是由阿里云推出的一款基于通义大模型的智能编码辅助工具&#xff0c;它通过先进的人工智能技术&#xff0c;为开发者提供了一系列的智能编码功能&#xff0c;极大地提升了编码效率和质量。以下是通义灵码的一些核心功能和应用案例。 核心功能 代码智能生成 通义灵码…
阅读更多...
视频降噪算法 Meshflow 介绍

视频降噪算法 Meshflow 介绍

介绍 Meshflow 视频降噪算法来自于 2017 年电子科技大学一篇高质量论文。 该论文提出了一个新的运动模型MeshFlow&#xff0c;它是一个空间平滑的稀疏运动场 (spatially smooth sparse motion field)&#xff0c;其运动矢量 (motion vectors) 仅在网格顶点 (mesh vertexes) 处…
阅读更多...
Spring+SpringMVC+Jsp实现校园二手交易系统

Spring+SpringMVC+Jsp实现校园二手交易系统

前言介绍 在社会快速发展的影响下&#xff0c;使校园二手交易系统的管理和运营比过去十年更加理性化。依照这一现实为基础&#xff0c;设计一个快捷而又方便的网上校园二手交易系统是一项十分重要并且有价值的事情。对于传统的管理控制模型来说&#xff0c;网上校园二手交易系…
阅读更多...
【AI】深度学习框架的期望与现实 机器学习编译尚未兑现其早期的一些承诺……

【AI】深度学习框架的期望与现实 机器学习编译尚未兑现其早期的一些承诺……

深度学习框架的期望与现实 机器学习编译尚未兑现其早期的一些承诺…… 来自&#xff1a;Axelera AI 资深软件工程师 Matthew Barrett 原帖是linkedin帖子&#xff1a; https://linkedin.com/posts/matthew-barrett-a49929177_i-think-its-fair-to-say-that-ml-compilation-ac…
阅读更多...
最新文章

Copyright @ 2022~2023