代码随想录刷题题Day12

刷题的第十二天，希望自己能够不断坚持下去，迎来蜕变。😀😀😀
刷题语言：C++
Day12 任务
● 层序遍历 10
● 226.翻转二叉树
● 101.对称二叉树 2

1 层序遍历

一口气做十题
102.二叉树的层序遍历
107.二叉树的层次遍历II
199.二叉树的右视图
637.二叉树的层平均值
429.N叉树的层序遍历
515.在每个树行中找最大值
116.填充每个节点的下一个右侧节点指针
117.填充每个节点的下一个右侧节点指针II
104.二叉树的最大深度
111.二叉树的最小深度

层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。
队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑

在这里插入图片描述
102.二叉树的层序遍历
在这里插入图片描述

层序遍历模板：
C++：

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
		vector<vector<int>> result;
		queue<TreeNode*> que;
		if (root != NULL) que.push(root);
		while (!que.empty())
		{
			int size = que.size();
			vector<int> vec;
			// 这里一定要使用固定大小size，不要使用que.size()
			while (size--)
			{
				TreeNode* node = que.front();
				que.pop();
				vec.push_back(node->val);
				if (node->left) que.push(node->left);
				if (node->right) que.push(node->right);
			}
			result.push_back(vec);
		}
		return result;
    }
};

107.二叉树的层次遍历II
在这里插入图片描述

思路：

把result数组反转一下

C++：

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        queue<TreeNode*> que;
        vector<vector<int>> result;
        if (root != NULL) que.push(root);
        while (!que.empty())
        {
            int size = que.size();
            vector<int> vec;
            while (size--)
            {
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            result.push_back(vec);
        }
        reverse(result.begin(), result.end());// 在这里反转一下数组
        return result;
    }
};

199.二叉树的右视图
在这里插入图片描述
思路：

判断是否遍历到单层的最后面的元素，如果是，就放进result数组中，随后返回result

C++：

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        queue<TreeNode*> que;
        vector<int> result;
        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();
                if (i == (size - 1)) result.push_back(node->val);// 将每一层的最后元素放入result数组
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
        }
        return result;
    }
};

637.二叉树的层平均值
在这里插入图片描述
思路：

层序遍历的时候把一层求个总和在取一个均值

C++：

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        queue<TreeNode*> que;
        vector<double> result;
        if (root != NULL) que.push(root);
        while (!que.empty())
        {
            double sum = 0;// 统计每一层的和
            int size = que.size();
            for (int i = 0; i < size; i++)
            {
                TreeNode* node = que.front();
                que.pop();
                sum += node->val;
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            result.push_back(sum / size);// 将每一层均值放进结果
        }
        return result;
    }
};

429.N叉树的层序遍历
在这里插入图片描述
思路：

一个节点有多个孩子,用for循环

C++：

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        queue<Node*> que;
        vector<vector<int>> result;
        if (root != NULL) que.push(root);
        while (!que.empty())
        {
            int size = que.size();
            vector<int> vec;
            while (size--)
            {
                Node* node = que.front();
                que.pop();
                vec.push_back(node->val);
                for (int i = 0; i < node->children.size(); i++)// 将节点孩子加入队列
                {
                    if (node->children[i]) que.push(node->children[i]);
                }
            }
            result.push_back(vec);
        }
        return result;
    }
};

515.在每个树行中找最大值
在这里插入图片描述
思路：

层序遍历，取每一层的最大值

C++：

class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        queue<TreeNode*> que;
        vector<int> result;
        if (root != NULL) que.push(root);
        while (!que.empty())
        {
            int size = que.size();
            int maxValue = INT_MIN;// 取每一层的最大值
            for (int i = 0; i < size; i++)
            {
                TreeNode* node = que.front();
                que.pop();
                maxValue = node->val > maxValue ? node->val : maxValue;
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            result.push_back(maxValue);// 把最大值放进数组
        }
        return result;
    }
};

class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        queue<TreeNode*> que;
        vector<int> result;
        if (root != NULL) que.push(root);
        while (!que.empty())
        {
            int size = que.size();
            vector<int> vec;
            for (int i = 0; i < size; i++)
            {
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            auto MAX = max_element(vec.begin(), vec.end());
            result.push_back(*MAX);
        }
        return result;
    }
};

116.填充每个节点的下一个右侧节点指针
在这里插入图片描述
思路：

在单层遍历的时候记录一下本层的头部节点，然后在遍历的时候让前一个节点指向本节点

C++：

class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> que;
        if (root != NULL) que.push(root);
        while (!que.empty())
        {
            int size = que.size();
            Node* node;
            Node* nodePre;
            for (int i = 0; i < size; i++)
            {
                if (i == 0) {
                    nodePre = que.front();// 取出一层的头结点
                    que.pop();
                    node = nodePre;
                }
                else {
                    node = que.front();
                    que.pop();
                    nodePre->next = node;// 本层前一个节点next指向本节点
                    nodePre = nodePre->next;
                }
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            nodePre->next = NULL;// 本层最后一个节点指向NULL
        }
        return root;
    }
};

117.填充每个节点的下一个右侧节点指针II
在这里插入图片描述
思路：

和上个题目一样

C++：

class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> que;
        if (root != NULL) que.push(root);
        while (!que.empty())
        {
            int size = que.size();
            Node* node;
            Node* nodePre;
            for (int i = 0; i < size; i++)
            {
                if (i == 0) {
                    nodePre = que.front();// 取出一层的头结点
                    que.pop();
                    node = nodePre;
                }
                else {
                    node = que.front();
                    que.pop();
                    nodePre->next = node;// 本层前一个节点next指向本节点
                    nodePre = nodePre->next;
                }
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            nodePre->next = NULL;// 本层最后一个节点指向NULL
        }
        return root;
    }
};

104.二叉树的最大深度
在这里插入图片描述
思路：

使用层序遍历是最为合适的，因为最大的深度就是二叉树的层数。在二叉树中，一层一层的来遍历二叉树，记录一下遍历的层数就是二叉树的深度
在这里插入图片描述

C++：

class Solution {
public:
    int maxDepth(TreeNode* root) {
        queue<TreeNode*> que;
        int depth = 0;
        if (root != NULL) que.push(root);
        while (!que.empty())
        {
            int size = que.size();
            depth++;// 记录深度
            while (size--)
            {
                TreeNode* node = que.front();
                que.pop();
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
        }
        return depth;
    }
};

111.二叉树的最小深度
在这里插入图片描述
思路：

当左右孩子都为空的时候，才说明遍历的最低点了。如果其中一个孩子为空则不是最低点

C++：

class Solution {
public:
    int minDepth(TreeNode* root) {
        int depth = 0;
        queue<TreeNode*> que;
        if (root == NULL) return 0;
        else que.push(root);
        while (!que.empty())
        {
            int size = que.size();
            depth++;// 记录最小深度
            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->left && !node->right) return depth;
            }
        }
        return depth;
    }
};

2 翻转二叉树

在这里插入图片描述
思路：
在这里插入图片描述

把每一个节点的左右孩子交换一下。注意只要把每一个节点的左右孩子翻转一下，就可以达到整体翻转的效果

递归法：
在这里插入图片描述
（1）确定递归函数的参数和返回值

参数：要传入节点的指针
返回值：其实也不需要，但是题目中给出的要返回root节点的指针，可以直接使用题目定义好的函数，所以就函数的返回类型为TreeNode*

TreeNode* invertTree(TreeNode* root)

（2）确定终止条件

if (root == NULL) return root;

（3）确定单层递归的逻辑
前序遍历：中 左 右

swap(root->left, root->right);
invert(root->left);
invert(root->right);

中序遍历：左 中 右

invert(root->left);
swap(root->left, root->right);
invert(root->left);

后序遍历：左 右 中

invert(root->left);
invert(root->right);
swap(root->left, root->right);

针对二叉树的问题，解题之前一定要想清楚究竟是前中后序遍历，还是层序遍历

C++：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        swap(root->left, root->right); // 中
        invertTree(root->left);        // 左
        invertTree(root->right);       // 右
        return root;
    }
};

迭代法：
深度优先遍历
C++：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == NULL) return root;
        stack<TreeNode*> st;
        st.push(root);
        while (!st.empty())
        {
            TreeNode* node = st.top();// 中
            st.pop();
            swap(node->left, node->right);
            if (node->right) st.push(node->right);// 右
            if (node->left) st.push(node->left);// 左
        }
        return root;
    }
};

广度优先遍历

层数遍历也是可以翻转这棵树的，因为层序遍历也可以把每个节点的左右孩子都翻转一遍

C++：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        while (!que.empty())
        {
            int size = que.size();
            while (size--)
            {
                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;
    }
};

3 对称二叉树

在这里插入图片描述
思路：

比较的是根节点的左子树与右子树是不是相互翻转的,比较的是两个树（这两个树是根节点的左右子树），所以在递归遍历的过程中，也是要同时遍历两棵树。

在这里插入图片描述
比较的是两个子树的里侧和外侧的元素是否相等
遍历顺序只能是后序遍历，因为要通过递归函数的返回值来判断两个子树的内侧节点和外侧节点是否相等。
因为要遍历两棵树而且要比较内侧和外侧节点，所以准确的来说是一个树的遍历顺序是左右中，一个树的遍历顺序是右左中
递归法：
（1）确定递归函数的参数和返回值
比较的是根节点的两个子树是否是相互翻转的，进而判断这个树是不是对称树，所以要比较的是两个树，参数自然也是左子树节点和右子树节点。
返回值自然是bool类型

bool compare(TreeNode* left, TreeNode* right)

（2）确定终止条件
要比较两个节点数值相不相同，首先要把两个节点为空的情况弄清楚！否则后面比较数值的时候就会操作空指针了。

  1. 左节点为空，右节点不为空，不对称，return false
  2. 左不为空，右为空，不对称 return false
  3. 左右都为空，对称，返回true
  4. 左右都不为空，比较节点数值，不相同就return false
if （left == NULL && right != NULL) return false;
else if (left != NULL && right == NULL) return false;
else if (left == NULL && right == NULL) return true;
else if (left->val != right->val) return false;

（3）确定单层递归的逻辑
处理 左右节点都不为空，且数值相同的情况

  1. 比较二叉树外侧是否对称：传入的是左节点的左孩子，右节点的右孩子。
  2. 比较内侧是否对称，传入左节点的右孩子，右节点的左孩子。
  3. 如果左右都对称就返回true ，有一侧不对称就返回false 。
bool outside = compare(left->left, right->right); // 左子树：左、 右子树：右
bool inside = compare(left->right, right->left);// 左子树：右、 右子树：左
bool result = outside && inside;// 左子树：中、 右子树：中
return result;

C++：

class Solution {
public:
    bool compare(TreeNode* left, TreeNode* right)
    {// 首先排除空节点的情况
        if (left == NULL && right != NULL) return false;
        else if (left != NULL && right == NULL) return false;
        else if (left == NULL && right == NULL) return true;
        // 排除了空节点，再排除数值不相同的情况
        else if (left->val != right->val) return false;
        // 此时就是：左右节点都不为空，且数值相同的情况
        // 此时才做递归，做下一层的判断
        bool outside = compare(left->left, right->right);
        bool inside = compare(left->right, right->left);
        bool result = outside && inside;
        return result;
    }
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        return compare(root->left, root->right);
    }
};

鼓励坚持十三天的自己😀😀😀

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

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

相关文章

恢复出厂设置后在 Android 上恢复照片的 6 种常用方法

恢复出厂设置后在 Android 上恢复照片的 6 种常用方法

恢复出厂设置可帮助您删除电子设备的所有信息并将其恢复到原始系统状态。但是&#xff0c;如果您不小心按下了恢复出厂设置按钮并从 Android 设备中删除了所有难忘的照片&#xff0c;该怎么办&#xff1f;好吧&#xff0c;您无需担心&#xff0c;因为可以通过以下一些方法来恢复…
阅读更多...
03 python循环语句

03 python循环语句

3.1while循环基本语法 # 演示while循环的基础应用i0 while i<100 :print(不到100)i 1while循环基本案例 import random num random.randint(1, 100) count 0 while True:guess_num int(input(随机输入数字&#xff1a;))count 1if guess_num num :print(jie shu)br…
阅读更多...
C++构造函数列表初始化的优点

C++构造函数列表初始化的优点

构造函数的执行可以分成两个阶段&#xff0c;初始化阶段和计算阶段&#xff0c;初始化阶段先于计算阶段。而初始化阶段就是对应着初始化列表那部分&#xff0c;而计算阶段就是构造函数的函数体部分。初始化阶段先于计算阶段执行。 #include<iostream>class Demon { publ…
阅读更多...
Cent OS7 磁盘挂载：扩展存储空间和自动挂载

Cent OS7 磁盘挂载：扩展存储空间和自动挂载

文章目录 &#xff08;1&#xff09;概述&#xff08;2&#xff09;查看磁盘使用情况&#xff08;3&#xff09;VMware虚拟机挂载磁盘&#xff08;4&#xff09;物理机磁盘挂载&#xff08;5&#xff09;ntfs硬盘处理 &#xff08;1&#xff09;概述 在Linux系统中&#xff0c…
阅读更多...
数据结构和算法 - 前置扫盲

数据结构和算法 - 前置扫盲

数据结构和算法 一、前置扫盲 1、数据结构分类 1.1 逻辑结构&#xff1a;线性与非线性 tip&#xff1a;逻辑结构揭示了数据元素之间的逻辑关系。 线性数据结构&#xff1a;元素间存在明确的顺序关系。 数据按照一定顺序排列&#xff0c;其中元素之间存在一个对应关系&#x…
阅读更多...
Axure 9基本元件，表单及表格元件简介，表单案例

Axure 9基本元件，表单及表格元件简介，表单案例

目录 一.基本元件 1.元件基本介绍 2.基本元件的使用 二.表单及表格元件 三.表单案例 四.简单简历绘制 一.基本元件 1.元件基本介绍 概述 - 在Axure RP中&#xff0c;元件是**构建原型图的基础模块**。 将元件从元件库里拖拽到画布中&#xff0c;即可添加元件到你的原型…
阅读更多...
【洛谷算法题】P1422-小玉家的电费【入门2分支结构】

【洛谷算法题】P1422-小玉家的电费【入门2分支结构】

&#x1f468;‍&#x1f4bb;博客主页&#xff1a;花无缺 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! 本文由 花无缺 原创 收录于专栏 【洛谷算法题】 文章目录 【洛谷算法题】P1422-小玉家的电费【入门2分支结构】&#x1f30f;题目描述&#x1f30f;输入格…
阅读更多...
2023前端面试题总结：JavaScript篇完整版

2023前端面试题总结：JavaScript篇完整版

前端面试题库 &#xff08;面试必备&#xff09; 推荐&#xff1a;★★★★★ 地址&#xff1a;前端面试题库 JavaScript基础知识 JavaScript有哪些数据类型&#xff0c;它们的区别&#xff1f; Number&#xff08;数字&#xff09;: 用于表示数值&#xff0c;可…
阅读更多...
【剑指offer|图解|二分查找】点名 + 统计目标成绩的出现次数

【剑指offer|图解|二分查找】点名 + 统计目标成绩的出现次数

&#x1f308;个人主页&#xff1a;聆风吟 &#x1f525;系列专栏&#xff1a;数据结构、剑指offer每日一练 &#x1f516;少年有梦不应止于心动&#xff0c;更要付诸行动。 文章目录 一. ⛳️点名1.1 题目1.2 示例1.3 限制1.4 解题思路一c代码 1.5 解题思路二c代码 二. ⛳️统…
阅读更多...
[算法每日一练]-双指针 （保姆级教程篇 1） #A-B数对 #求和 #元音字母 #最短连续子数组 #无重复字符的最长子串 #最小子串覆盖 #方块桶

[算法每日一练]-双指针 （保姆级教程篇 1） #A-B数对 #求和 #元音字母 #最短连续子数组 #无重复字符的最长子串 #最小子串覆盖 #方块桶

目录 A-B数对 解法一&#xff1a;双指针 解法二&#xff1a;STL二分查找 解法三&#xff1a;map 求和 元音字母 最短连续子数组 无重复字符的最长子串 最小子串覆盖 方块桶 双指针特点&#xff1a;双指针绝不回头 A-B数对 解法一&#xff1a;双指针 先把数列排列成…
阅读更多...
电脑出现msvcr120_1.dll丢失如何解决，怎么修复

电脑出现msvcr120_1.dll丢失如何解决，怎么修复

一、msvcr120.dll_1.dll文件的作用&#xff1a; msvcr120.dll_1.dll是一个动态链接库文件&#xff0c;它是Microsoft Visual C Redistributable Package的一部分。该文件包含了许多常用的函数和类&#xff0c;这些函数和类被许多应用程序所共享和使用。因此&#xff0c;当您在…
阅读更多...
成功的云转型之路需要考虑的基本因素

成功的云转型之路需要考虑的基本因素

云计算如今已经变得无处不在&#xff0c;并显著影响着日常生活的各个方面。然而&#xff0c;重要的是要注意云计算技术是不断发展的。最近向远程工作的转变促使企业加快数字化转型&#xff0c;更多地采用云计算服务。 即使在新冠疫情消退之后&#xff0c;云计算技术的采用也获得…
阅读更多...
【Hive】

【Hive】

一、Hive是什么 Hive是一款建立在Hadoop之上的开源数据仓库系统&#xff0c;将Hadoop文件中的结构化、半结构化数据文件映射成一张数据库表&#xff0c;同时提供了一种类SQL语言&#xff08;HQL&#xff09;&#xff0c;用于访问和分析存在Hadoop中的大型数据集。Hive的核心是将…
阅读更多...
java代码编写twitter授权登录

java代码编写twitter授权登录

在上一篇内容已经介绍了怎么申请twitter开放的API接口。 下面介绍怎么通过twitter提供的API&#xff0c;进行授权登录功能。 开发者页面设置 首先在开发者页面开启“用户认证设置”&#xff0c;点击edit进行信息编辑。 我的授权登录是个网页&#xff0c;并且只需要进行简单的…
阅读更多...
Nginx快速入门

Nginx快速入门

nginx准备 文本概述参考笔记 狂神&#xff1a;https://www.kuangstudy.com/bbs/1353634800149213186 前端vue打包 参考&#xff1a;https://blog.csdn.net/weixin_44813417/article/details/121329335 打包命令&#xff1a; npm run build:prod nginx 下载 网址&#x…
阅读更多...
大模型应用_FastGPT

大模型应用_FastGPT

1 功能 整体功能&#xff0c;想解决什么问题 官方说明&#xff1a;FastGPT 是一个基于 LLM 大语言模型的知识库问答系统&#xff0c;提供开箱即用的数据处理、模型调用等能力。同时可以通过 Flow 可视化进行工作流编排&#xff0c;从而实现复杂的问答场景&#xff01;个人体会…
阅读更多...
竞赛保研 python 爬虫与协同过滤的新闻推荐系统

竞赛保研 python 爬虫与协同过滤的新闻推荐系统

1 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; python 爬虫与协同过滤的新闻推荐系统 &#x1f947;学长这里给一个题目综合评分(每项满分5分) 难度系数&#xff1a;3分工作量&#xff1a;3分创新点&#xff1a;4分 该项目较为新颖&…
阅读更多...
道路坑洞数据集（坑洞目标检测）VOC+YOLO格式650张

道路坑洞数据集（坑洞目标检测）VOC+YOLO格式650张

路面坑洞的形成原因是由于设计、施工、养护处理不当、控制不适和受气候、环境、地质、水文等自然因素影响&#xff0c;以及车辆的运行和车辆超载运行导致路面破损&#xff0c;出现坑洞的现象。 路面坑洞的分类&#xff1a; &#xff08;1&#xff09;路面混凝土板中坑洞&…
阅读更多...
如何使用 Redis 快速实现分布式锁？

如何使用 Redis 快速实现分布式锁？

本文我们来讨论如何使用 Redis 快速实现分布式锁。 分布式锁有很多种解决方案&#xff0c;前面简单介绍过&#xff0c;Redis 可以通过 set key 方式来实现分布式锁&#xff0c;但实际情况要更加复杂&#xff0c;比如如何确保临界资源的串行执行&#xff0c;如何及时释放&#…
阅读更多...
人工智能_机器学习065_SVM支持向量机KKT条件_深度理解KKT条件下的损失函数求解过程_公式详细推导_---人工智能工作笔记0105

人工智能_机器学习065_SVM支持向量机KKT条件_深度理解KKT条件下的损失函数求解过程_公式详细推导_---人工智能工作笔记0105

之前我们已经说了KKT条件,其实就是用来解决 如何实现对,不等式条件下的,目标函数的求解问题,之前我们说的拉格朗日乘数法,是用来对 等式条件下的目标函数进行求解. KKT条件是这样做的,添加了一个阿尔法平方对吧,这个阿尔法平方肯定是大于0的,那么 可以结合下面的文章去看,也…
阅读更多...
最新文章

Copyright @ 2022~2023