C++从零开始的打怪升级之路(day45)

2024-03-07 21:12

本文主要是介绍C++从零开始的打怪升级之路(day45),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

这是关于一个普通双非本科大一学生的C++的学习记录贴

在此前,我学了一点点C语言还有简单的数据结构,如果有小伙伴想和我一起学习的,可以私信我交流分享学习资料

那么开启正题

今天分享的是关于二叉树的题目

1.根据二叉树创建字符串

606. 根据二叉树创建字符串

给你二叉树的根节点 root ,请你采用前序遍历的方式,将二叉树转化为一个由括号和整数组成的字符串,返回构造出的字符串。

空节点使用一对空括号对 "()" 表示,转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对

仔细理解题目,可以发现这是一套基础的递归题,要注意的是括号的省略与否,左子树存在右子树不存在则可以省略,左子树不存在右子树存在则不能省略

class Solution {
public:string tree2str(TreeNode* root) {string s;if(root == nullptr)return s;s += (to_string(root->val));if(root->left){s += "(";s += tree2str(root->left);s += ")";} else if(root->right){s += "()";}if(root->right){s += "(";s += tree2str(root->right);s += ")";} return s;}
};

这是ac代码

2.二叉树的层序遍历1

102. 二叉树的层序遍历

给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)

二叉树的层序遍历,借助queue即可,但是这里需要一层一层地输出,就需要做一些细微地调整,具体看下面的代码

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> vv;if(root == nullptr)return vv;queue<TreeNode*> q;q.push(root);while(!q.empty()){vector<int> v;int sz = q.size();for(int i = 0; i < sz; ++i){TreeNode* front = q.front();q.pop();v.push_back(front->val);if(front->left)q.push(front->left);if(front->right)q.push(front->right);}vv.push_back(v);}return vv;}
};

3.二叉树的层序遍历2

107. 二叉树的层序遍历 II

给你二叉树的根节点 root ,返回其节点值 自底向上的层序遍历 。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)

这题和上面很像,但是是倒着遍历,直接操作好像没什么头绪,但是我们可以在上面题目操作完的基础上reverse以下vv,即可得到结果

class Solution {
public:vector<vector<int>> levelOrderBottom(TreeNode* root) {vector<vector<int>> vv;if(root == nullptr)return vv;queue<TreeNode*> q;q.push(root);while(!q.empty()){vector<int> v;int sz = q.size();for(int i = 0; i < sz; ++i){TreeNode* front = q.front();q.pop();v.push_back(front->val);if(front->left)q.push(front->left);if(front->right)q.push(front->right);}vv.push_back(v);}reverse(vv.begin(), vv.end());return vv;}
};

这是ac代码

4.二叉树的最近公共祖先

236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

很明显,又是一道递归的题目,要找到最近公共祖先,我们从根开始判断,如果有一个就是根,那么直接返回根,如果不是,但是,要判断的两个结点,在树的两边子树上,那么根就是最近公共祖先,反之,向左右子树递归解决

class Solution {
public:bool Find(TreeNode* root, TreeNode* x){   if(root == nullptr)return false;if(root == x)return true;return Find(root->left, x) || Find(root->right, x);}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root == q || root == p)return root;bool qleft, qright, pleft, pright;qleft = Find(root->left, q);    pleft = Find(root->left, p);    qright = Find(root->right, q);    pright = Find(root->right, p);if((qleft && pright) || (pleft && qright))return root;if(qleft && pleft)return lowestCommonAncestor(root->left, p, q);if(qright && pright)return lowestCommonAncestor(root->right, q, p);return nullptr;}
};

5.二叉树与双向链表

二叉搜索树与双向链表_牛客题霸_牛客网

输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表

1.要求不能创建任何新的结点,只能调整树中结点指针的指向。当转化完成以后,树中节点的左指针需要指向前驱,树中节点的右指针需要指向后继
2.返回链表中的第一个节点的指针
3.函数返回的TreeNode,有左右指针,其实可以看成一个双向链表的数据结构

4.你不用输出双向链表,程序会根据你的返回值自动打印输出

题目给的二叉树是搜索二叉树,又叫做排序二叉树,要构造一个升序的双向链表,很显然要用到中序遍历,而中序遍历的时候,找不到他应该连的左与右,所以我们借助一个子函数来完成任务

通过cur和prev与中序遍历实现双向链表的构建,要注意的是,prev作为“贯穿”全局的角色,传参时要传引用

class Solution {
public:void _Convert(TreeNode* cur, TreeNode*& prev){if(cur == nullptr)return;_Convert(cur->left, prev);//处理cur->left = prev;if(prev)prev->right = cur;prev = cur;_Convert(cur->right, prev);}TreeNode* Convert(TreeNode* pRootOfTree) {TreeNode* prev = nullptr;_Convert(pRootOfTree, prev);TreeNode* head = pRootOfTree;while(head && head->left)head = head->left;return head;}
};

这是ac代码

新手写博客,有不对的位置希望大佬们能够指出,也谢谢大家能看到这里,让我们一起学习进步吧!

这篇关于C++从零开始的打怪升级之路(day45)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/784856

相关文章

将Mybatis升级为Mybatis-Plus的详细过程

《将Mybatis升级为Mybatis-Plus的详细过程》本文详细介绍了在若依管理系统(v3.8.8)中将MyBatis升级为MyBatis-Plus的过程,旨在提升开发效率,通过本文,开发者可实现... 目录说明流程增加依赖修改配置文件注释掉MyBATisConfig里面的Bean代码生成使用IDEA生

C++ 中的 if-constexpr语法和作用

《C++中的if-constexpr语法和作用》if-constexpr语法是C++17引入的新语法特性,也被称为常量if表达式或静态if(staticif),:本文主要介绍C++中的if-c... 目录1 if-constexpr 语法1.1 基本语法1.2 扩展说明1.2.1 条件表达式1.2.2 fa

C++中::SHCreateDirectoryEx函数使用方法

《C++中::SHCreateDirectoryEx函数使用方法》::SHCreateDirectoryEx用于创建多级目录,类似于mkdir-p命令,本文主要介绍了C++中::SHCreateDir... 目录1. 函数原型与依赖项2. 基本使用示例示例 1:创建单层目录示例 2:创建多级目录3. 关键注

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

C++ 各种map特点对比分析

《C++各种map特点对比分析》文章比较了C++中不同类型的map(如std::map,std::unordered_map,std::multimap,std::unordered_multima... 目录特点比较C++ 示例代码 ​​​​​​代码解释特点比较1. std::map底层实现:基于红黑

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中,模板是实现泛型编程

利用Python和C++解析gltf文件的示例详解

《利用Python和C++解析gltf文件的示例详解》gltf,全称是GLTransmissionFormat,是一种开放的3D文件格式,Python和C++是两个非常强大的工具,下面我们就来看看如何... 目录什么是gltf文件选择语言的原因安装必要的库解析gltf文件的步骤1. 读取gltf文件2. 提