当前位置： 首页 > news >正文

C++算法题目分享：二叉搜索树相关的习题

news 2025/8/18 13:12:06

        我们之前介绍了二叉搜索树的相关知识。作为算法领域的重要数据结构，二叉搜索树也是面试中的高频考点。本文将重点讲解几个二叉搜索树的典型习题。

        相关代码已经上传至作者的个人gitee：CPP 学习代码库: C++代码库新库，旧有C++仓库满员了喜欢请支持一下

目录

前言

根据二叉树创建字符串​编辑​

拓展：to_string函数的介绍

核心作用与规则：

        stoi函数的介绍

二叉树的层序遍历

二叉树的层序遍历2

二叉树的最近公共祖先

        算法一：

        算法二：

将二叉搜索树转化为排序的双向链表

    从前序与中序遍历序列构造二叉树​编辑            

二叉树前序非递归

二叉树中序非递归

二叉树后序非递归

前言

        二叉搜索树具有以下重要特性：

  1. 左子树上所有节点的值都小于它的根节点的值
  2. 右子树上所有节点的值都大于它的根节点的值
  3. 左右子树也必须是二叉搜索树

        这种数据结构在实际开发中有广泛应用场景，比如：

  • 数据库索引的实现
  • 文件系统的目录结构
  • 内存管理中的内存分配算法
  • 游戏开发中的场景管理、

根据二叉树创建字符串​

        思路：

        左边为空，右不为空，不能省略空括号；其余情况下空均可以省略空括号

/*** 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:string tree2str(TreeNode* root) {string str; if(root==nullptr)return str;str+=to_string(root->val);//特殊情况处理//左不为空需要递归获取子树//左为空，右不为空，左边的括号需要保留if(root->left!=nullptr||root->right!=nullptr){str+='(';str+=tree2str(root->left);str+=')';}//右不为空需要递归获取子树//右为空任何情况下都不需要括号if(root->right!=nullptr){str+='(';str+=tree2str(root->right);str+=')';}return str;}
};

拓展：to_string函数的介绍

​

核心作用与规则：

  1. 参数要求（遵循"右不为空"原则）：

    • 必须在括号内提供数值参数（int/double/long 等）

    • 空括号 to_string() ❌ 违反规则（编译错误）

    • 无参数版本不存在 ❌

  2. 返回值（遵循"左边为空"原则）：

    • 总是返回新的 std::string 对象

    • 返回值不能忽略（必须接收或使用）

类型转换规则：

输入类型输出示例特殊规则
int 123"123"直接转换
double 3.14"3.140000"默认补足6位小数
bool true❌ 不支持需手动转换
char 'A'"65" (ASCII值)非字符转换，需用string(1,'A')

        stoi函数的介绍

​

二叉树的层序遍历

        

        思路1：双队列。队列1存节点指针，队列2存节点层数。记录每个节点的层数。

当前节点的孩子层数+1.

        思路2：层序遍历的时候添加一个遍历levelsize，记录每一层的数据个数。树不为空的情况下，第一层levelsize=1，循环控制结束后第一层出完了第二层进队列。队列中size就是第二层的数据个数。以此类推，假设levelsize是第n层个数，因为层序遍历思想为当前层节点出队列，带入下一层节点（子节点），循环控制第n层出完了，第n+1节点也就进队列了。队列size就是下一层的levelsize。

/*** 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:vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*>q;int levelsize=0;//记录当前层数多少个数据if(root){q.push(root);levelsize=1;}vector<vector<int>>vv;//层序遍历while(!q.empty()){vector<int>v;//控制一层一层出while(levelsize--){   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);//当前层出完了下一层节点都进队列，队列数据个数就是下一次节点个数levelsize=q.size();}return vv;}
};

二叉树的层序遍历2

        相比于前一题逆置一下

/*** 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:vector<vector<int>> levelOrderBottom(TreeNode* root) {//思路2vector<vector<int>>vv;queue<TreeNode*> q1;int levelsize=0;if(root){q1.push(root); levelsize=1;}    while(levelsize>0){//控制一层一层出vector<int>v;while(levelsize--){TreeNode*front=q1.front();q1.pop();v.push_back(front->val);//下一层的孩子入队列if (front->left)q1.push(front->left);if (front->right)q1.push(front->right); }vv.push_back(v);//当前层出完了，下一层都进队列了//q.size()就是下一层节点个数levelsize=q1.size();}//相比于前一题逆置一下reverse(vv.begin(),vv.end());return vv;}
};

二叉树的最近公共祖先

        

        算法一：

       思路： 观察我们发现两个节点的公共祖先必须保证一个在祖先的左侧一个在祖先的右侧。如果都在同一侧则不需要找另一侧。比如下图的左侧只需要找左子树，右图只需要找右子树。

class Solution 
{
public://算法一：//时间复杂度O(N^2)bool IsInTree(TreeNode* root,TreeNode* x){if(root==nullptr)return false;//相等肯定在树上return root==x||IsInTree(root->left,x)||IsInTree(root->right,x);}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q){//空树不需要找if (root == nullptr)return nullptr;//要找的节点自己就是二叉树根节点if (root == p || root == q)return root;bool pInleft = IsInTree(root->left, p);bool pInright = !pInleft;bool qInleft = IsInTree(root->left, q);bool qInright = !qInleft;//p和q在二叉树两侧，root就是公共祖先//都在左去左子树查找//都在右去右子树查找if ((pInleft && qInright) || (pInright && qInleft)){return root;}//要么都左要么都右else if (pInleft && qInleft){return lowestCommonAncestor(root->left, p, q);}//写法1：else if (pInright && qInright){return lowestCommonAncestor(root->right, p, q);}return nullptr;//写法2：// else // {//     return lowestCommonAncestor(root->right,p,q);// }}};

        但是实际上这种算法时间复杂度过高，仅作为参考

        算法二：

        如果求出两个节点到根的路径，则可以转化为链表相交的问题。

        如：6到3 的路径为6-》5-》3。4到3的路径为-》2-》5-》3。

        则可以利用前序遍历的思路找x节点的路径。遇到root先入栈，因为root不是x，但是root可能是分支节点。

        本质上就是前序查找+栈记录查找路径

        如果左右子树都没有x，则说明root不是根-》x的路径，所以要pop出栈，回退去其他分支查找。

class Solution 
{
public://算法2：//深度遍历的层序查找，用栈记录路径bool GetPath(TreeNode*root,TreeNode* x,stack<TreeNode*>& path){//空树没有路径if(root==nullptr)return false;path.push(root);//经过路径if(root==x)return true;//如果不再公共节点上//左子树去找if(GetPath(root->left,x,path))return true;//右子树去找if(GetPath(root->right,x,path))return true;//如果都不在那就不在路径上path.pop();return false;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q){stack<TreeNode*>pPath,qPath;GetPath(root,p,pPath);GetPath(root,q,qPath);//找交点while(pPath.size()!=qPath.size()){//长的先走if(pPath.size()>qPath.size()){pPath.pop();}else{qPath.pop();}}//在同时走找交点while(pPath.top()!=qPath.top()){pPath.pop();qPath.pop();}return pPath.top();}
};

将二叉搜索树转化为排序的双向链表

        

        思路1：中序遍历二叉树，遍历顺序是有序的，将节点放到vector中，再将链表前后节点关系进行修改。

        思路2：中序遍历二叉树，遍历顺序是有序的，遍历过程中修改左指针为前驱和右指针为后继。记录一个cur和prev，cur为当前中序遍历的节点，prev为之前中序遍历的节点，cur->left指向prev，cur->right无法指向中序的下一个，因为不知大中序下一个是谁，但是prev->right指向cur。也就是说每个结点的左是在遍历到当前节点的时候修改为前驱的，节点的右是遍历到下一个节点的时候修改指向后继的。

class Solution 
{
public://当前的中序遍历void InOrderConvent(Node*cur,Node*&prev ){if(cur==nullptr)return ;InOrderConvent(cur->left,prev);//cur中序遍历//cur指向前一个变成前驱cur->left=prev;//前一个结点的后继if(prev){prev->right =cur;}prev=cur;InOrderConvent(cur->right,prev);}Node* treeToDoublyList(Node* root) {if(root==nullptr)return nullptr;Node*prev=nullptr;InOrderConvent(root,prev);Node*head=root;while(head->left){head=head->left;}//循环链表head->left=prev;prev->right=head;return head;}
};

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

        思路：前序确定跟，中序分割出左右子树。

        

/*** 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://prei：前序区间TreeNode* build(vector<int>& preorder, vector<int>& inorder,int&prei,int Inbegin,int Inend){//不存在的区间if(Inbegin>Inend)return nullptr;//前序遍历确定跟TreeNode* root=new TreeNode(preorder[prei]);//中序分隔左右子树int rooti=Inbegin;while(rooti<=Inend){//找到了if(preorder[prei]==inorder[rooti]){break;}else{rooti++;}}prei++;//分隔为三段[Inbegin,rooti-1]  rooti  [rooti+1,Inend]//构建左子树root->left=build(preorder,inorder,prei,Inbegin,rooti-1);//构建右子树root->right=build(preorder,inorder,prei,rooti+1,Inend);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int i=0;return build(preorder,inorder,i,0,inorder.size()-1);    }
};

二叉树前序非递归

        二叉树的递归遍历虽然写法简单，但是因为递归需要开栈帧，如果二叉树深度比较深那么可能导致栈溢出，所以需要非递归写法。

        非递归实现思想

        要迭代⾮递归实现⼆叉树前序遍历，⾸先还是要借助递归的类似的思想，只是需要把结点存在栈中， ⽅便类似递归回退时取⽗路径结点。

        跟这⾥不同的是，这⾥把⼀棵⼆叉树分为两个部分：

         1. 先访问左路结点

         2. 再访问左路结点的右⼦树

        这⾥访问右⼦树要以循环从栈依次取出这些结点，循环⼦问题的思想访问左路结点的右⼦树。

         中序和后序跟前序的思路完全⼀致，只是前序先访问根还是后访问根的问题。

        后序稍微⿇烦⼀些，因 为后序遍历的顺序是左⼦树右⼦树根，当取到左路结点的右⼦树时，需要想办法标记判断右⼦树是否 访问过了，如果访问过了，就直接访问根，如果访问过需要先访问右⼦树

/*** 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:vector<int> preorderTraversal(TreeNode* root) {stack<TreeNode*>st;TreeNode*cur=root;vector<int>v;while(cur||!st.empty()){//循环开始代表访问一棵树的开始//先访问左路结点，左路结点入栈while(cur){v.push_back(cur->val);st.push(cur);cur=cur->left;}//依次取左路节点右子树出来访问TreeNode*news=st.top();st.pop();//子问题的方式访问右子树//循环子问题cur=news->right;}return v;}
};

二叉树中序非递归

        

       

/*** 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:vector<int> inorderTraversal(TreeNode* root) {stack<TreeNode*> st;   // 辅助栈：存储待回溯的节点TreeNode* cur = root;  // 当前遍历节点（初始为根节点）vector<int> v;         // 存储遍历结果// 当存在未处理节点或栈非空时继续遍历while (cur || !st.empty()) {// 阶段1：深度优先访问左子树// 将当前节点和所有左子节点入栈（直到叶子节点）while (cur) {st.push(cur);      // 当前节点入栈（后续回溯用）cur = cur->left;   // 持续向左深入}// 阶段2：回溯处理根节点TreeNode* top = st.top();  // 获取栈顶节点（当前最左节点）st.pop();                 // 弹出已访问节点v.push_back(top->val);    // 访问节点值（相当于处理根节点）// 阶段3：转向右子树// 将当前指针设为右子节点（若存在右子树则进入下一轮循环处理）cur = top->right;  // 关键：以右子树为新的起点继续遍历}return v;}
};

 

二叉树后序非递归

        

        取到一个左路结点的时候左子树已经访问过了；如果左路结点右子树不为空，右子树没有访问，则上一个访问的是左子树的根；如果左路结点右子树不为空，右子树已经访问，则上一个访问的是右子树的根

        

/*** 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:vector<int> postorderTraversal(TreeNode* root) {stack<TreeNode*> st;    // 辅助栈：存储待回溯的节点TreeNode* cur = root;   // 当前遍历节点（初始为根节点）TreeNode* prev = nullptr; // 记录前次访问的节点（关键：判断右子树是否已访问）vector<int> v;          // 存储遍历结果while (cur || !st.empty()) {// 阶段1：深度优先访问左子树// 将当前节点和所有左子节点入栈（直到叶子节点）while (cur) {st.push(cur);cur = cur->left;  // 持续向左深入}// 获取栈顶节点（此时左子树已访问完）TreeNode* top = st.top();/* 关键判断：何时可以访问当前节点？条件1：右子树为空（无右子树）条件2：右子树已被访问（prev == top->right）满足任一条件即可访问当前节点 */if (top->right == nullptr || top->right == prev) {v.push_back(top->val);  // 访问节点值st.pop();               // 弹出已访问节点prev = top;             // 更新前次访问节点（标记为已处理）} // 右子树存在且未访问else {cur = top->right;  // 转向右子树（以相同逻辑处理右子树）prev = nullptr;     // 重置prev（可选，逻辑已隐含）}}return v;}
};

        本期算法题分享到此结束，如果你喜欢请点个赞关注支持一下，谢谢

http://www.xdnf.cn/news/1319203.html

相关文章：

  • 【165页PPT】基于IPD的研发项目管理（附下载方式）
  • RISC-V汇编新手入门
  • 计算机视觉（一）：nvidia与cuda介绍
  • Android 组件封装实践：从解耦到架构演进
  • Python使用数据类dataclasses管理数据对象
  • metasploit 框架安装更新遇到无法下载问题如何解决
  • Redis面试精讲 Day 24：Redis实现限流、计数与排行榜
  • C#中List、Path、字符串操作等常用方法总结
  • ​​Vue 3 开发速成手册
  • 说一下事件传播机制
  • Python注解
  • Python入门第7课：异常处理机制：让你的程序更健壮（try-except详解）
  • 配置 NVIDIA RTX 5090 + sm_120 + flashattention，已跑通一个大模型 ~~
  • C语言（12）——进阶函数
  • Day3--滑动窗口与双指针--2461. 长度为 K 子数组中的最大和，1423. 可获得的最大点数，1052. 爱生气的书店老板
  • 数字货币的法律属性与监管完善路径探析
  • 实变函数中集合E的边界与其补集的边界是否相等
  • Android中使用Compose实现各种样式Dialog
  • Dify 从入门到精通（第 40/100 篇）：Dify 的企业级权限管理
  • Mutually aided uncertainty
  • Windchill 11.0使用枚举类型自定义实用程序实现生命周期状态管理
  • Makefile介绍（Makefile教程）（C/C++编译构建、自动化构建工具）
  • 计算机网络 TCP、UDP 区别
  • 从需求到部署全套方案：餐饮服务许可证数据可视化分析系统的大数据技术实战
  • Bee1.17.25更新Bug,完善功能.不支持NOSQL,分库分表Sharding(2.X版有)
  • C语言网络编程TCP通信实战:客户端↔服务器双向键盘互动全流程解析
  • 模拟实现 useEffect 功能
  • 【R语言】R 语言中打印含有双引号的字符串时会出现 “\” 的原因解析
  • 基于STM32单片机智能RFID刷卡汽车位锁桩设计
  • 基于51单片机汽车自动照明灯超声波光敏远近光灯设计