【C++】二叉树进阶OJ题

news/2025/1/16 3:36:59/

​🌠 作者：@阿亮joy.
🎆专栏：《吃透西嘎嘎》
🎇 座右铭：每个优秀的人都有一段沉默的时光，那段时光是付出了很多努力却得不到结果的日子，我们把它叫做扎根
在这里插入图片描述

目录

    • 👉根据二叉树创建字符串👈
    • 👉二叉树的层序遍历 I 和 II👈
    • 👉二叉树的最近公共祖先👈
    • 👉二叉搜索树与双向链表👈
    • 👉从前序与中序遍历序列构造二叉树👈
    • 👉从后序与中序遍历序列构造二叉树👈
    • 👉总结👈

👉根据二叉树创建字符串👈

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

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

在这里插入图片描述

思路：本道题就是前序遍历创建字符串，创建字符串时需要用括号将左右子树括起来。当左右子树都为空时，可以省略掉左右子树的括号。当左子树不为空，右子树为空时，可以省略掉右子树的括号。当左子树为空，右子树不为空时，左子树的括号不能省略掉。

class Solution 
{
public:string tree2str(TreeNode* root) {if(root == nullptr)return string();string str;str += to_string(root->val);// 左边不为空或者左边为空右边不为空，需要加括号if(root->left || root->right){str += '(';str += tree2str(root->left);str += ')';}// 右边不为空，需要加括号if(root->right){str += '(';str += tree2str(root->right);str += ')';}return str;}
};

在这里插入图片描述

以上的解法还可以优化一下，因为返回值是string，会存在比较多的拷贝构造，我们可以通过引用和调用子函数的方式来优化。

class Solution 
{
private:void _tree2str(TreeNode* root, string& str){if(root == nullptr)return;str += to_string(root->val);if(root->left || root->right){str += '(';str += tree2str(root->left);str += ')';}if(root->right){str += '(';str += tree2str(root->right);str += ')';}}
public:string tree2str(TreeNode* root) {string str;_tree2str(root, str);return str;}
};

在这里插入图片描述

👉二叉树的层序遍历 I 和 II👈

二叉树的层序遍历 I

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

在这里插入图片描述

思路一：

  • 首先定义一个队列q和当前层的节点个数levelSize = 0
  • 当根节点root不为空时，根节点如队列q，且将levelSize设置为 1
  • 当队列不为空时，while循环进行。while循环内部用for循环来控制出一层的节点，出的同时需要将所出节点的左右孩子也让入队列中（如果有的话）。
  • 当for结束后，队列的size就是下一层的节点个数了。
  • while循环结合后，就能够得到二维数组了。

在这里插入图片描述

class Solution 
{
public:vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> q;size_t levelSize = 0;if(root){q.push(root);levelSize = 1;}vector<vector<int>> vv;while(!q.empty()){vector<int> v;// 控制一层一层出for(int i = 0; i < levelSize; ++i){TreeNode* top = q.front();v.push_back(top->val);q.pop();if(top->left)q.push(top->left);if(top->right)q.push(top->right);}vv.push_back(v);// 当前层出完了,下一层的节点都进队列了,队列的size就是下一层的节点个数levelSize = q.size();}return vv;}
};

在这里插入图片描述

思路二：

  • 先申请一个队列q，如果根节点root不为空，根节点入队列
  • 然后定义两个TreeNode*变量curend = root和nextend = nullptr，curend为当前层的最后一个节点，next是下一层的最后一个节点。
  • 当队列不为空，while循环继续。队头所出的节点记为front，将front->val尾插到一位数组v中。然后front的左右孩子入队列（如果有的话），入的同时将nextend更新为最后入队列的节点。
  • 当所出节点front等于当前层最后的节点curend时，说明当前层所有节点的值已经收集完毕，即可将一维数组v尾插到二维数组vv中。然后还需要做以下操作：清空一维数组v；准备收集下一层节点的值，更新当前层的最后一个节点curend = nextend；next置为空（可以不做，最好做）
  • while循环结束，二维数组vv存储的就是层序遍历的结果。
class Solution 
{
public:vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> q;if(root){q.push(root);}vector<vector<int>> vv;TreeNode* curend = root;    // 当前层最后一个节点TreeNode* nextend = nullptr;    // 下一层最后一个节点vector<int> v;while(!q.empty()){TreeNode* front = q.front();v.push_back(front->val);q.pop();if(front->left){q.push(front->left);nextend = front->left;}if(front->right){q.push(front->right);nextend = front->right;}// 当front等于curend时,说明当前层所有节点的值已收集完毕// 可以准备收集下一层节点的值if(front == curend){vv.push_back(v);    v.clear();  // 清空一维数组curend = nextend;   // 更新curend}}return vv;}
};

class Solution 
{
public:vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> q;if(root){q.push(root);}vector<vector<int>> vv;TreeNode* curend = root;    // 当前层最后一个节点TreeNode* nextend = nullptr;    // 下一层最后一个节点vector<int> v;while(!q.empty()){TreeNode* front = q.front();v.push_back(front->val);q.pop();// 只要是下一层节点入了队列,就需要更新nextend为入队列的节点if(front->left){q.push(front->left);nextend = front->left;}if(front->right){q.push(front->right);nextend = front->right;}// 当front等于curend时,说明当前层所有节点的值已收集完毕// 可以准备收集下一层节点的值if(front == curend){vv.push_back(v);    v.clear();  // 清空一维数组curend = nextend;   // 更新curend}}return vv;}
};

在这里插入图片描述
注：以上两种方法还有用来求二叉树的最大宽度。

其实还有一种思路：双队列也可以解决这道题。一个队列存储节点，另一个队列存节点的所在层数，大家可以尝试一下。

在这里插入图片描述

二叉树的层序遍历 II

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

在这里插入图片描述

我们只需要将二叉树的层序遍历 I 中得到的二维数组vv反转一下就能够解决这道题了。

class Solution 
{
public:vector<vector<int>> levelOrderBottom(TreeNode* root) {queue<TreeNode*> q;size_t levelSize = 0;if(root){q.push(root);levelSize = 1;}vector<vector<int>> vv;while(!q.empty()){vector<int> v;// 控制一层一层出for(int i = 0; i < levelSize; ++i){TreeNode* top = q.front();v.push_back(top->val);q.pop();if(top->left)q.push(top->left);if(top->right)q.push(top->right);}vv.push_back(v);// 当前层出完了,下一层的节点都入队列了,队列的size就是下一层节点的个数levelSize = q.size();}reverse(vv.begin(), vv.end());return vv;}
};

在这里插入图片描述

👉二叉树的最近公共祖先👈

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

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

在这里插入图片描述
在这里插入图片描述

思路一：

在这里插入图片描述

class Solution 
{
private:// 查找节点x是否在以sub为根节点的树中bool Find(TreeNode* sub, TreeNode* x){if(sub == nullptr)return false;return sub == x|| Find(sub->left, x)|| Find(sub->right, x);}
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root == nullptr)return nullptr;// 其中一个节点为根节点,则最近公共祖先为根节点if(root == p || root == q)return root;// p、q在根节点的左右子树中bool pInLeft, pInRight, qInLeft, qInRight;pInLeft = Find(root->left, p);pInRight = !pInLeft;qInLeft = Find(root->left, q);qInRight = !qInLeft;if(pInLeft && qInLeft)  // p、q都在根节点的左子树中,转化成子问题return lowestCommonAncestor(root->left, p, q);else if(pInRight && qInRight)   // p、q都在根节点的右子树中,转化成子问题return lowestCommonAncestor(root->right, p, q);else    // p、q一个在左,另一个在右，最近公共祖先为根节点return root;}
};

在这里插入图片描述

注：因为 p 和 q 一定在树中，所以 p 在左子树，那么它一定不会在右子树中，q 同理。这种解法的时间复杂度为O(h*N)，h为树的高度，N为节点的个数。

思路二：
这种思路是求出从根节点root到p和q的路径，路径用栈来存储。因为路径长短不一样，所以先让长的弹出长度差个节点，然后两个栈一起弹出节点直至栈顶节点相同，那么栈顶节点就是p和q的最近公共祖先。这种解法的思路类似于链表相交的思路，时间复杂度为O(N)。

在这里插入图片描述

class Solution 
{
private:bool FindPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& path){if(root == nullptr)return false;path.push(root);if(root == x)   // 根节点就是p、qreturn true;if(FindPath(root->left, x, path))   // p、q在root的左子树中return true;if(FindPath(root->right, x, path))  // p、q在root的右子树中return true;path.pop();     // 经过root无法到达p、q,所以要将root弹出return false;}
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {stack<TreeNode*> pPath, qPath;FindPath(root, p, pPath);   // pPath中储存的是root到p的路径FindPath(root, q, qPath);   // qPath中储存的是root到q的路径// 路径长的弹出长度差个节点while(pPath.size() != qPath.size()){if(pPath.size() > qPath.size())pPath.pop();elseqPath.pop();}// 栈顶节点相等时,栈顶节点就是最近公共祖先while(pPath.top() != qPath.top()){pPath.pop();qPath.pop();}return pPath.top();}
};

在这里插入图片描述

思路三：

思路三是思路一的精简版本，时间复杂度为O(N)。

在这里插入图片描述

class Solution 
{
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {// root为空或者是p、q中的一样都要返回自己if(root == nullptr || root == p || root == q)return root;TreeNode* InLeft = lowestCommonAncestor(root->left, p, q);TreeNode* InRight = lowestCommonAncestor(root->right, p, q);// InLeft和InRight都不为空,则根节点为最近公共祖先if(InLeft && InRight)return root;// InLeft和InRight谁不为空,谁就是最近公共祖先return InLeft ? InLeft : InRight;}
};

在这里插入图片描述

👉二叉搜索树与双向链表👈

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

在这里插入图片描述
在这里插入图片描述

思路：本道题要求左指针 left 指向中序的前一个节点，右指针 right 指向中序的后一个节点。我们可以采用prev来记录当前节点cur的前一个节点，那么prev->right = cur, cur->left = prev，这样就可以将二叉搜索树转化成双向链表了。注意：prev是Node*的引用，这样才能链接起来。

class Solution 
{
private:void InordertreeToDoublyList(Node* cur, Node*& prev){if(cur == nullptr)return;InordertreeToDoublyList(cur->left, prev);cur->left = prev;if(prev != nullptr)prev->right = cur;prev = cur;InordertreeToDoublyList(cur->right, prev);}
public:Node* treeToDoublyList(Node* root) {// 根节点为空,直接返回nullptr即可if(root == nullptr)return nullptr;Node* prev = nullptr;InordertreeToDoublyList(root, prev);// 找到中序第一个节点Node* first = root;while(first->left){first = first->left;}// 找到中序最后一个节点Node* last = root;while(last->right){last = last->right;}// 第一个节点与最后一个节点链接起来形成双向循环链表first->left = last;last->right = first;return first;}
};

在这里插入图片描述

👉从前序与中序遍历序列构造二叉树👈

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

在这里插入图片描述
在这里插入图片描述

思路：前序结果创建树，中序分割左右子树。子树区间确认是否继续递归创建子树，区间不存在则是空树。

class Solution 
{
private:TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder, int& preI, int inBegin, int inEnd){if(inBegin > inEnd)return nullptr;// 构建根TreeNode* root = new TreeNode(preorder[preI]);// 用中序结果来分割左右子树int inI = inBegin;while(inI <= inEnd){if(inorder[inI] == root->val)break;else++inI;}// [inBegin, inI - 1] inI [inI + 1, inEnd]// 先构建左子树再构建右子树++preI;    // 找出左右子树的根root->left = _buildTree(preorder, inorder, preI, inBegin, inI - 1);root->right = _buildTree(preorder, inorder, preI, inI + 1, inEnd);return root;}
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int i = 0;return _buildTree(preorder, inorder, i, 0, inorder.size() - 1);}
};

在这里插入图片描述
注：因为preI是遍历前序数组preinorde的下标，整个递归遍历中都要使用，所以需要传引用。如果不是传引用而是传值的话，左子树构建好返回。因为preI不是引用，只是形参，无法将上一次递归的结果保留下来，那么这样就无法找到右子树的根了，也就无构建右子树了。

👉从后序与中序遍历序列构造二叉树👈

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

在这里插入图片描述
在这里插入图片描述

思路：后序结果创建树，中序分割左右子树。子树区间确认是否继续递归创建子树，区间不存在则是空树。因为后序遍历序列是左子树、右子树、根，所以后序遍历序列的最后一个元素是根节点，位于它前面的是右子树的根节点。所以先要构建右子树，再来构建左子树。最后把根和左右子树链接在一起，二叉树就构建完成了。

class Solution 
{
private:TreeNode* _buildTree(vector<int>& inorder, vector<int>& postorder, int& posI, int inBegin, int inEnd){if(inBegin > inEnd)return nullptr;TreeNode* root = new TreeNode(postorder[posI]);// 中序分割左右子树int inI = inBegin;while(inI <= inEnd){if(inorder[inI] == root->val)break;else++inI;}// 先构建右子树再构建左子树// [inBegin, inI - 1] inI [inI + 1, inEnd]--posI;root->right = _buildTree(inorder, postorder, posI, inI + 1, inEnd);;root->left = _buildTree(inorder, postorder, posI, inBegin, inI - 1);return root;}
public:TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {int i = postorder.size() - 1;return _buildTree(inorder, postorder, i, 0, inorder.size() - 1);}
};

在这里插入图片描述
注：中序与后序遍历序列是无法确定唯一的一块树的，使用两个遍历结果确定树的结构， 其中有一个遍历结果必须要是中序遍历结果。

👉总结👈

本篇博客主要讲解了二叉树进阶的 OJ 题，每道题都是非常经典的面试题。那么以上就是本篇博客的全部内容了，如果大家觉得有收获的话，可以点个三连支持一下！谢谢大家！💖💝❣️


http://www.ppmy.cn/news/12851.html

相关文章

2022视频编码招聘面经

2022视频编码招聘面经

视频编码相关工作大概包括以下几个方向&#xff1a; 1. 视频编码标准&#xff0c;主要参与国际国内编码标准制定工作&#xff0c;招聘公司大多都是大厂&#xff0c;坑位较少 2. 软件编码器优化&#xff0c;主要是对codec内核的加速和性能提升&#xff0c;互联网公司需求较多 3.…
阅读更多...
【网络安全】渗透测试之linux信息收集

【网络安全】渗透测试之linux信息收集

前言 在内网中linux的服务器是占大多数的&#xff0c;主要原因分为以下几点 1.便宜&#xff0c;linux大多为免费的&#xff0c;Windows Server是收费的&#xff0c;对于企业来说为了节约成本&#xff0c;大量采用linux服务器。 2.轻便&#xff0c;linux主要是对服务器进行服务的…
阅读更多...
Transformer学习笔记1

Transformer学习笔记1

模型分类&#xff1a;GPT类型&#xff1a; auto-regressive&#xff08;decoder模型&#xff0c;过去时刻的输出也是现在的输入&#xff0c;例如要得到y8还需要知道y1到y7&#xff0c;但不能使用y9&#xff0c;例如用于文本生成任务&#xff09;GPTGPT2CTRLTransformer XLBERT类…
阅读更多...
【科研试剂】16-Heptadecynoic acid，93813-16-2，16-庚二酸

【科研试剂】16-Heptadecynoic acid，93813-16-2，16-庚二酸

【中文名称】16-庚二酸【英文名称】 16-Heptadecynoic acid&#xff0c;16-Heptadecynoic COOH【结 构 式】【CAS】93813-16-2【分子式】C17H30O2【分子量】266.43【纯度标准】95%【包装规格】1g&#xff0c;5g&#xff0c;10g【是否接受定制】可进行定制&#xff0c;定制时间周…
阅读更多...
拉伯证券|锂离子动力电池有哪些优缺点？锂离子电池的优缺点详解

拉伯证券|锂离子动力电池有哪些优缺点？锂离子电池的优缺点详解

锂离子动力电池是20世纪开发成功的新型高能电池。这种电池的负极是石墨等资料&#xff0c;正极用磷酸铁锂、钴酸锂、钛酸锂等。70年代进入实用化。因其具有能量高、电池电压高、工作温度规模宽、贮存寿命长等优点&#xff0c;已广泛应用于军事和民用小型电器中。 锂离子动力电池…
阅读更多...
3D游戏引擎系统源码C++本科毕业设计，C++ 3D引擎源码，渲染系统使用的OpenGL 及 OpenGL ES

3D游戏引擎系统源码C++本科毕业设计，C++ 3D引擎源码，渲染系统使用的OpenGL 及 OpenGL ES

Effective 3D Engine 渲染系统使用的OpenGL 及 OpenGL ES&#xff0c;Windows上OpenGL ES使用AMD的ES模拟器。 环境部署 完整代码下载地址&#xff1a;3D游戏引擎系统源码C本科毕业设计 Win32环境配置 编辑器 将proj_win32/RenderSystem/gles_renderSystem/GLES/dll 中的d…
阅读更多...
嵌入式Linux从入门到精通之第一节：软件安装

嵌入式Linux从入门到精通之第一节：软件安装

Linux安装 ubuntu环境安装 1.安装Vmware Player虚拟机：双击VMware-player.exe，一路next即可； 2.打开虚拟机，点击Creat a New Virtual Machine; 3.选择稍后设置； 4.选择Linux，ubuntu； 5.选择虚拟机名称和路径； 6.硬盘选择50G； 7.改变虚拟机设置，进行内存相关设置，内…
阅读更多...
Pandas 数据清洗

Pandas 数据清洗

Pandas 数据清洗数据清洗是对一些没有用的数据进行处理的过程。很多数据集存在数据缺失、数据格式错误、错误数据或重复数据的情况&#xff0c;如果要对使数据分析更加准确&#xff0c;就需要对这些没有用的数据进行处理。在这个教程中&#xff0c;我们将利用 Pandas包来进行数…
阅读更多...
最新文章

Copyright @ 2022~2023