Studying-代码随想录训练营day14| 226.翻转二叉树、101.对称二叉树、104.二叉树的最大深度、111.二叉树的最小深度

第十四天,(ง •_•)ง💪💪,编程语言:C++

目录

226.翻转二叉树

101.对称二叉树

100.相同的树 

572.另一个树的子树

104.二叉树的最大深度

559.n叉树的最大深度

111.二叉树的最小深度

总结


226.翻转二叉树

文档讲解:代码随想录翻转二叉树

视频讲解:手撕翻转二叉树

题目:

初看:本题翻转二叉树不仅仅是把根节点的左右子树进行了翻转,也把子节点下面的左右子树都进行了翻转。需要对所有中间节点(非叶子节点)进行处理。

代码:前序遍历(递归法)

//时间复杂度O(n)
//空间复杂度O(n)
class Solution {
public:void reverseNode(TreeNode* root) {if (root == nullptr || (root->left == nullptr && root->right == nullptr)) return;TreeNode* tmp = root->left; //中root->left = root->right;root->right = tmp;//swap(root->left, root->right);reverseNode(root->left); //左reverseNode(root->right);//右}TreeNode* invertTree(TreeNode* root) { reverseNode(root);return root;}
};

代码: 层次遍历(广度优先遍历)

//时间复杂度O(n)
//空间复杂度O(n)
class Solution {
public:TreeNode* invertTree(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) 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;}
};

注意:此题能够使用前序遍历和后序遍历,逻辑基本一致,但如果采用中序遍历的方式,要注意把中节点处理后,右子树就变成了左子树,左子树就变成了右子树,因此下次处理的时候仍应处理的是左子树(原右子树)

class Solution {
public:TreeNode* invertTree(TreeNode* root) {if (root == NULL) return root;invertTree(root->left);         // 左swap(root->left, root->right);  // 中invertTree(root->left);         // 注意 这里依然要遍历左孩子,因为中间节点已经翻转了return root;}
};

101.对称二叉树

文档讲解:代码随想录对称二叉树

视频讲解:手撕对称二叉树

题目:

初看:对称二叉树从根节点开始,往下比较左右节点,之后往下需要分为两条道路,一条左右子树的外层节点,一条比较左右子树的内层节点。因此实际上是比较左右两棵树是否相等。

代码:后序遍历(递归法)

//时间复杂度O(n)
//空间复杂度O(n)
class Solution {
public:bool compare(TreeNode* left, TreeNode* right) {if(left == NULL && right == NULL) return true; //都为空返回trueelse if(left == NULL || right == NULL) return false; //有一个为空另一个不为空(都为空前面判断了)返回falseelse if(left->val != right->val) return false; //都不为空但是值不相等else { //都不为空且值相等,向下继续遍历bool outside = compare(left->left, right->right); //外侧比较bool inside = compare(left->right, right->left); //内测比较return outside && inside; //都为true才返回true;}}//递归法bool isSymmetric(TreeNode* root) {if(root == nullptr) return true;return compare(root->left, root->right);}
};

学习:

  1. 本题需要遍历两棵树而且要比较内侧和外侧的节点,所以准确的来说是一个树的遍历顺序是左右中,一个树的遍历顺序是右左中。这都可以理解为一种后序遍历,把孩子的信息反馈到父节点身上。
  2. 本题的递归三部曲:①确定递归函数的参数和返回值:本题需要比较左右子树,因此参数肯定为左子树和右子树的节点,其次本题是判断正确,因此返回bool类型。②确定终止条件:用清楚节点存在的情况:左节点为空,右节点不为空;左不为空,右为空;左右都为空;左右都不为空,比较节点数值。③确定单层递归逻辑:左右节点都不为空,且数值相同时才进入单层递归的逻辑。单层递归的逻辑就是比较:比较二叉树外侧是否对称,传入的是左节点的左孩子,右节点的右孩子;比较内侧是否对称,传入左节点的右孩子,右节点的左孩子;如果左右都对称就返回true ,有一侧不对称就返回false。

代码:迭代法,注意加入节点的顺序即可

class Solution {
public://迭代法bool isSymmetric(TreeNode* root) {queue<TreeNode*> que;if(root == nullptr) return true;que.push(root->left);que.push(root->right);while(!que.empty()) {TreeNode* left = que.front();que.pop();TreeNode* right = que.front();que.pop();if(left == NULL && right == NULL) continue; //都为空进行后序节点比较else if(left == NULL || right == NULL) return false; //有一个为空另一个不为空(都为空前面判断了)返回falseelse if(left->val != right->val) return false; //都不为空但是值不相等else {//按顺序加入节点que.push(left->left);   // 加入左节点左孩子que.push(right->right); // 加入右节点右孩子que.push(left->right);  // 加入左节点右孩子que.push(right->left);  // 加入右节点左孩子}}return true;}
};

注意:迭代法中使用了队列,但实际上并不是层序遍历,而是仅仅通过一个容器来成对的存放我们要比较的元素,知道这一本质之后就发现,用队列,用栈,甚至用数组,都是可以的。

其他题目:

100.相同的树 

题目:

初看:和左右子树对称一样,只不过没有了 根节点,比较的节点也变为了一一对应的关系。

代码:

//时间复杂度O(min(m,n))
//空间复杂度O(min(m,n))
class Solution {
public:bool isSameTree(TreeNode* p, TreeNode* q) {queue<TreeNode*> que;if (!p && !q) return true;//载入两个节点依次进行判断que.push(p);que.push(q);while(!que.empty()) {//取出需要比较的节点TreeNode* node1 = que.front(); que.pop();TreeNode* node2 = que.front(); que.pop();if (node1 == nullptr && node2 == nullptr) continue; //都为空进行下一轮判断else if (node1 == nullptr || node2 == nullptr) return false; //有一个不为空,返回错误else if (node1->val != node2->val) return false; //都不为空但是值不等else {//注意载入节点的顺序que.push(node1->left);que.push(node2->left);que.push(node1->right);que.push(node2->right);}}return true;}
};

572.另一个树的子树

题目:

初看: 本题事实上与找到相同的树是一样的,只不过它还需要遍历每一个节点。

代码:

//时间复杂度O(n*m)
class Solution {
public://暴力匹配==寻找相同的树bool compare(TreeNode* root, TreeNode* subRoot) {queue<TreeNode*> que;//载入两个节点依次进行判断que.push(root);que.push(subRoot);while(!que.empty()) {//取出需要比较的节点TreeNode* node1 = que.front(); que.pop();TreeNode* node2 = que.front(); que.pop();if (node1 == nullptr && node2 == nullptr) continue; //都为空进行下一轮判断else if (node1 == nullptr || node2 == nullptr) return false; //有一个不为空,返回错误else if (node1->val != node2->val) return false; //都不为空但是值不等else {//注意载入节点的顺序que.push(node1->left);que.push(node2->left);que.push(node1->right);que.push(node2->right);}}return true;}bool isSubtree(TreeNode* root, TreeNode* subRoot) {//广度优先遍历+暴力匹配//广度优先遍历queue<TreeNode*> que;if (root != nullptr) que.push(root);if (subRoot == nullptr) return true;bool result;while (!que.empty()) {TreeNode* node = que.front(); que.pop();if (node->val == subRoot->val) {result = compare(node, subRoot);cout << result << endl;if(result == true) return true;}if(node->left) que.push(node->left);if(node->right) que.push(node->right);}return false;}
};

注意:本题还可以采用KMP算法,和哈希筛选等方法,但过于复杂不利于理解,故没有给出。可前往力扣查看对应例题详解。


104.二叉树的最大深度

文本讲解: 代码随想录二叉树的最大深度

视频讲解:手撕二叉树的最大深度

题目:

学习:昨天使用了层次遍历的方式求解本题,实际上本题也可以使用深度优先遍历的方式来进行求解。本题是要查找树的最大深度,实际上这与树的高度是一一对应的,根节点的高度就是树的最大深度,因此可以采取前序遍历和后序遍历的方式,来查找根节点的高度。

代码:后序遍历(递归法)

注:相当于每次递归后depth深度+1,之后返回左子树和右子树之中最大的那个深度。

//时间复杂度O(n)
//空间复杂度O(n)
class Solution {
public:int getdepth(TreeNode* node) {if (node == NULL) return 0;int leftdepth = getdepth(node->left);       // 左int rightdepth = getdepth(node->right);     // 右int depth = 1 + max(leftdepth, rightdepth); // 中return depth;}int maxDepth(TreeNode* root) {return getdepth(root);}
};

代码:前序遍历(递归法)

注:前序遍历相比之下复杂一些,这是因为它需要先处理节点,再进行递归,因此需要一个辅助量result,每次递归前进行赋值判断。实际含义就是先找寻左子树中最大深度,保存最大深度,然后看右子树有没有更大的深度,再进行赋值。

class Solution {
public:int result;void getdepth(TreeNode* node, int depth) {result = depth > result ? depth : result; // 中if (node->left == NULL && node->right == NULL) return ;if (node->left) { // 左depth++;    // 深度+1getdepth(node->left, depth);depth--;    // 回溯,深度-1}if (node->right) { // 右depth++;    // 深度+1getdepth(node->right, depth);depth--;    // 回溯,深度-1}return ;}int maxDepth(TreeNode* root) {result = 0;if (root == NULL) return result;getdepth(root, 1);return result;}
};

其他题目:

559.n叉树的最大深度

题目:

学习:本题和求二叉树的最大深度逻辑基本相同,只不过是把左右孩子换成了一个数组,增加一个for循环遍历孩子即可。

代码:层次遍历

//时间复杂度O(n)
//空间复杂度O(n)
class Solution {
public:int maxDepth(Node* root) {//最大深度就是需要遍历的层数queue<Node*> que;int depth = 0; //记入深度if (root != nullptr) que.push(root);while (!que.empty()) {int size = que.size();//每进行循环深度加1depth++;for (int i = 0; i < size; i++) {Node* node = que.front();que.pop();for (auto it = node->children.begin(); it != node->children.end(); it++) {que.push(*it);}}}return depth;}
};

代码:后序遍历(递归法)

//时间复杂度O(n)
//空间复杂度O(n)
class Solution {
public:int maxDepth(Node* root) {if (root == 0) return 0;int depth = 0;//求孩子的最大深度for (int i = 0; i < root->children.size(); i++) {depth = max (depth, maxDepth(root->children[i]));}//加上根节点return depth + 1;}
};

111.二叉树的最小深度

文档讲解:代码随想录二叉树的最小深度

视频讲解:手撕二叉树的最小深度

题目:

学习: 昨天同样也是用了层次遍历的方法求解本题,本题也能够使用迭代法进行处理,但需要注意的是,只有遍历到叶子节点(左右节点都没有时)才算是遍历到了合法的深度位置。

代码:后序遍历(递归)

//时间复杂度O(n)
//空间复杂度O(n)
class Solution {
public:int getDepth(TreeNode* node) {if (node == NULL) return 0;int leftDepth = getDepth(node->left);           // 左int rightDepth = getDepth(node->right);         // 右// 中//只有遍历到一个树的叶子节点(没有孩子)才算是终止// 当一个左子树为空,右不为空,这时并不是最低点,它可能还有孩子if (node->left == NULL && node->right != NULL) { return 1 + rightDepth;}   // 当一个右子树为空,左不为空,这时并不是最低点,它可能还有孩子if (node->left != NULL && node->right == NULL) { return 1 + leftDepth;}//两边都有孩子才取最小的深度int result = 1 + min(leftDepth, rightDepth);return result;}int minDepth(TreeNode* root) {return getDepth(root);}
};

代码:层次遍历

class Solution {
public:int minDepth(TreeNode* root) {//最小深度,就是在遍历每一层节点的时候,如果发现该节点没有子节点则停下循环。queue<TreeNode*> que;int depth = 0; //记入深度if (root != nullptr) que.push(root);while (!que.empty()) {int size = que.size();//每进行循环深度加1depth++;for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();if (node->left) que.push(node->left);if (node->right) que.push(node->right);if (node->right == nullptr && node->left == nullptr) {return depth;}}}return depth;}
};

总结

二叉树遍历有两种方式:广度优先遍历,深度优先遍历。深度优先遍历又分为三种:前序遍历、后序遍历、中序遍历。广度优先遍历就是层次遍历。

二叉树遍历的代码有三种:递归法求前中后序遍历,迭代法使用栈求前中后序遍历,迭代法使用队列求层次遍历。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

建筑八大员证报名一寸彩色照片要求及手机自拍方法解读

在建筑行业&#xff0c;八大员证的持有者是广受尊重的专业人士。然而&#xff0c;要成为一名合格的八大员&#xff0c;首先必须通过资格审核和报名流程。其中重要的一步就是提交一寸彩色照片&#xff0c;以确保个人信息准确无误。那么&#xff0c;你是否清楚报名时照片的要求以…

milvus元数据解析工具milvusmetagui介绍使用

简介 milvusmetagui是一款用来对milvus的元数据进行解析的工具&#xff0c;milvus的元数据存储在etcd上&#xff0c;而且经过了序列化&#xff0c;通过etcd-manager这样的工具来查看是一堆二进制乱码&#xff0c;因此开发了这个工具对value进行反序列化解析。 在这里为了方便交…

深圳中小企业融资攻略,贷款方法大盘点!

中小企业融资这事&#xff0c;可不是一个简单的事情。资金对中小企业来说&#xff0c;就像血液对人体一样重要。企业发展离不开资金支持&#xff0c;特别是在今年这个环境下&#xff0c;政策对中小企业还挺友好的。今天讲解一下中小微企业常用的几种贷款方法。希望能让大家更明…

基于STM32和人工智能的自动驾驶小车系统

目录 引言环境准备自动驾驶小车系统基础代码实现&#xff1a;实现自动驾驶小车系统 4.1 数据采集模块4.2 数据处理与分析4.3 控制系统4.4 用户界面与数据可视化应用场景&#xff1a;自动驾驶应用与优化问题解决方案与优化收尾与总结 1. 引言 随着人工智能和嵌入式系统技术的…

pikachu靶场之XSS漏洞测试

一、环境配置 1.pikachu官网下载 下载地址&#xff1a;https://github.com/zhuifengshaonianhanlu/pikachu 2.百度网盘&#xff08;里面含有pikachu跟phpstudy&#xff09; 链接&#xff1a;pikachu下载 密码&#xff1a;abcd 配置&#xff1a;pikachu下载及安装-图文详解…

【尚庭公寓SpringBoot + Vue 项目实战】登录管理(十八)

【尚庭公寓SpringBoot Vue 项目实战】登录管理&#xff08;十八&#xff09; 文章目录 【尚庭公寓SpringBoot Vue 项目实战】登录管理&#xff08;十八&#xff09;1、登录业务介绍2、接口开发2.1、获取图形验证码2.2、登录接口2.3、获取登录用户个人信息 1、登录业务介绍 登…

keil5显示内存和存储占用百分比进度条工具

简介 [Keil5_disp_size_bar] 以进度条百分比来显示keil编译后生成的固件对芯片的内存ram和存储flash的占用情况, 并生成各个源码文件对ram和flash的占比整合排序后的map信息的表格和饼图。 原理是使用C语言遍历当前目录找到keil工程和编译后生成的map文件 然后读取工程文件和m…

shadertoy-安装和使用

一、安装vscode 安装vscode流程 二、安装插件 1.安装glsl编辑插件 2.安装shader toy插件 三、创建glsl文件 test.glsl文件 float Grid(float size, vec2 fragCoord) {vec2 r fragCoord / size;vec2 grid abs(fract(r - 0.5) - 0.5) / fwidth(r);float line min(grid…

Weevil-Optimizer象鼻虫优化算法的matlab仿真实现

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.本算法原理 5.完整程序 1.程序功能描述 Weevil-Optimizer象鼻虫优化算法的matlab仿真实现&#xff0c;仿真输出算法的优化收敛曲线&#xff0c;对比不同的适应度函数。 2.测试软件版本以及运行结果展示…

李宏毅2023机器学习作业HW06解析和代码分享

ML2023Spring - HW6 相关信息&#xff1a; 课程主页 课程视频 Sample code HW06 视频 HW06 PDF 个人完整代码分享: GitHub | Gitee | GitCode P.S. HW06 是在 Judgeboi 上提交的&#xff0c;出于学习目的这里会自定义两个度量的函数&#xff0c;不用深究&#xff0c;遵循 Sugge…

MySQL数据库的字段属性(navicat)

Unsigned&#xff1a;无符号 无符号的整数 声明了该列不能声明为负数 zerofill&#xff1a;填充零 不满足长度时&#xff0c;用0进行填充 如&#xff1a;int&#xff08;3&#xff09;&#xff0c;5 ——> 005 位置在无符号的下方 自增 通常理解为自增&…

《算法设计与分析》第五六章:回溯法与分支限界法

文章目录 回溯法分支限界法一、本章作业1.活动安排问题2.旅行商问题3.单源最短路径4.任务分配问题 二、算法积累1.回溯法求解01背包问题2.回溯法求解最大团问题3.回溯法求解n皇后问题4.回溯法求解地图着色5.回溯法求解哈密尔顿图6.回溯法求活动安排7.分支限界法求01背包问题8.分…

DIVE INTO DEEP LEARNING 36-49

文章目录 36. Data augmentation36.1 Training with enhanced data36.2 Enhancement measures36.3 Data augmentation summary 37. Fine tuning37.1 Fine tuning Introduce37.2 Fine tuning Step37.3 Fine tuning summary 38. Object detection38.1 Object detection38.2 Edge …

SpringBoot+Vue实现Excel文档导入和导出

1.准备工作 1.1.前端程序 在前端首先加上批量导出的按钮&#xff0c;如下 <el-button size"small" type"warning" plain click"exportData"> 批量导出 </el-button> 在添加了点击事件之后&#xff0c;在methods中要与之对应的添加上…

汽车IVI中控开发入门及进阶(二十七):车载摄像头vehicle camera

前言: 在车载IVI、智能座舱系统中,有一个重要的应用场景就是视频。视频应用又可分为三种,一种是直接解码U盘、SD卡里面的视频文件进行播放,一种是手机投屏,就是把手机投屏软件已视频方式投屏到显示屏上显示,另外一种就是对视频采集设备(主要就是摄像头Camera)的视频源…

3ds Max软件下载安装:3D建模软件 轻松开启你的建模之旅!

3ds Max&#xff0c;在建模过程中&#xff0c;网格建模和NURBS建模两大技术发挥着不可或缺的作用。网格建模允许用户通过顶点、边和面等元素的调整&#xff0c;精确地塑造出模型的形态&#xff1b;而NURBS建模则以其优秀的曲线和曲面处理能力&#xff0c;为设计师们提供了更为平…

二分+ST表+递推,Cf 1237D - Balanced Playlist

一、题目 1、题目描述 2、输入输出 2.1输入 2.2输出 3、原题链接 Problem - 1237D - Codeforces 二、解题报告 1、思路分析 case3提示我们一件事情&#xff1a;如果存在某个位置永远不停止&#xff0c;那么所有位置都满足永远不停止 很容易证明 随着下标右移&#xff0c…

【Ruby基础01】windows和termux中搭建Ruby开发环境

windows下环境搭建 railsinstaller官方git地址 按照文档安装git、nodejs、yarn&#xff0c;安装教程百度一下。railsinstall可以从release页面下载最新版本4.1.0。 安装完成如下 安装RubyMine 下载RubyMine RubyMine下载地址 安装激活 下载文件&#xff0c;按照里面的流程…

Houdini到UE地形流程

目录 Houidni地形制作 UE地形设置 Houdini engine插件安装 B站参考视频 Houidni地形制作 使用Terrain的HeightField相关节点制作地形&#xff1b;设置地形相关的材质层&#xff08;如rock、soil、grass等&#xff09;&#xff0c;注意材质的重叠&#xff1b; //detail层级&…

Python网络爬虫4-实战爬取pdf

1.需求背景 爬取松产品中心网站下的家电说明书。这里以冰箱为例&#xff1a;松下电器-冰箱网址 网站分析&#xff1a; 第一步&#xff1a; 点击一个具体的冰箱型号&#xff0c;点击了解更多&#xff0c;会打开此型号电器的详情页面。 第二步&#xff1a;在新打开的详情页面中…