二叉搜索树经典笔试题【力扣、牛客】

文章目录

  • 1.根据二叉树创建字符串
  • 2. 二叉树的层序遍历
  • 3.二叉树的层序遍历Ⅱ
  • 4.二叉树的最近公共祖先
    • 1.法一:定位p、q在左还是右 分类讨论
    • 2.法二:利用stack求出p、q路径 求相交值
  • 5.二叉搜索树与双向链表
    • 1.法一:递归:递归过程修正指针指向
    • 2.数组:将二叉搜索树进行中序遍历可以得到由小到大的顺序排列
  • 6.前序中序遍历序列构造二叉树
  • 7.中序后序遍历序列构造二叉树
  • 8.二叉树的前序遍历【非递归】
  • 9.二叉树的中序遍历【非递归】
  • 10.二叉树的后序遍历【非递归】
    • 1.法一:栈模拟实现递归
    • 2.法二:前序遍历修改

在这里插入图片描述

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

根据二叉树创建字符串在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

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* eft, TreeNode* right): val(x), left(left), right(right){}
};//图一分析:
//左不空 (左递归直至遇空返回上一层) 
//然后在当层判断右子树 
//右空 (返回上层 + )
//右不空 (左递归直至遇空返回上一层)
//然后在当层判断右子树 
//右空 (返回上一层 + )//图二分析:
//左不空 (左递归直至遇空返回上一层) 
//然后在当层判断右子树 
//右不空 (左递归直至遇空返回上一层)
//然后在当层判断右子树 
//右空 (返回上层 + )
//右不空 (左递归直至遇空返回上一层)//左不空 右空  --省略
// 左空时第一个if两个条件才判断完
//左空   右空  --省略
//左空  右不空 --不省略
class Solution
{
public:string tree2str(TreeNode* root){if (root == nullptr)return "";string str = to_string(root->val);//遍历完根后遍历左 遍历左的前提是左不空 如果左空看看右空不空//如果右也空没必要遍历 return//如果右不空 正常遍历if (root->left || root->right){str += '(';str += tree2str(root->left);str += ')';}if (root->right) //遍历完左后遍历右 遍历右的前提是右不空 //右不空 正常遍历 右空 【看注释知右空的一律省略 直接return】{str += '(';str += tree2str(root->right);str += ')';}return str;}
};

2. 二叉树的层序遍历

二叉树的层序遍历
在这里插入图片描述
在这里插入图片描述
点击 二叉树【C】 查看上篇博客中的层序遍历
在这里插入图片描述

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* eft, TreeNode* right): val(x), left(left), right(right){}
};class Solution 
{
public:vector<vector<int>> levelorder(TreeNode* root) {queue<TreeNode*> q;int LevelNodeCount = 0;if (root){q.push(root);LevelNodeCount = 1;}vector<vector<int>> vv;while (!q.empty()){vector<int> v;while (LevelNodeCount--){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);LevelNodeCount = q.size();}return vv;}
};

3.二叉树的层序遍历Ⅱ

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

class Solution 
{
public:vector<vector<int>> levelorder(TreeNode* root) {queue<TreeNode*> q;int LevelNodeCount = 0;if (root){q.push(root);LevelNodeCount = 1;}vector<vector<int>> vv;while (!q.empty()){vector<int> v;while (LevelNodeCount--){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);LevelNodeCount = q.size();}reverse(vv.begin(), vv.end());return vv;}
};

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

二叉树的最近公共祖先
在这里插入图片描述在这里插入图片描述

1.法一:定位p、q在左还是右 分类讨论

T(N)=O(N^2)
最坏情况:树为单链即均在左侧或右侧,p、q均在单侧的底部
判断p、q的左右侧时 n-2 n-1
假设p、q均在左侧 接下来递归到左子树 继续判断p、q中是否为根?在左?在右?n-3 n-2 …

class Solution 
{
public:bool IsInTree(TreeNode* root, TreeNode* x){if (root == nullptr)return false;return root == x|| IsInTree(root->left, x)|| IsInTree(root->right,x);}//求p、q的最近公共祖先TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q){if (root == nullptr)return nullptr;//p、q其中一个是根 那么根就为objif (root == p || root == q)return root;//判断p、q在左 ?右bool pInLeft = IsInTree(root->left, p);bool pInRight = !pInLeft;bool qInLeft = IsInTree(root->left, q);bool qInRight = !qInLeft;//一左一右==》root为objif ((pInLeft && qInRight) || (pInRight && qInLeft))return root;//均左==》递归到左子树if (pInLeft && qInLeft)return lowestCommonAncestor(root->left, p, q);//均右==》递归到右子树elsereturn lowestCommonAncestor(root->right, p, q);}
};

2.法二:利用stack求出p、q路径 求相交值

class Solution
{
public:bool GetPath(TreeNode* root, TreeNode* pobj, stack<TreeNode*>& route){if (root == nullptr)return false;route.push(root);if (root == pobj)return true;if (GetPath(root->left, pobj, route))return true;if (GetPath(root->right, pobj, route))return true;route.pop();return false;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {stack<TreeNode*> pRoute;stack<TreeNode*> qRoute;GetPath(root, p, pRoute);GetPath(root, q, qRoute);//找路径相遇点while (pRoute.size() != qRoute.size()){if (pRoute.size() > qRoute.size())pRoute.pop();elseqRoute.pop();}while (pRoute.top() != qRoute.top()){pRoute.pop();qRoute.pop();}return pRoute.top();}
};

5.二叉搜索树与双向链表

二叉搜索树与双向链表
在这里插入图片描述
在这里插入图片描述

1.法一:递归:递归过程修正指针指向

class Solution
{
public: //中序遍历void InOrderConvert(TreeNode* cp, TreeNode*& prv){if (cp == nullptr)return;InOrderConvert(cp->left, prv);//一路向左 遇空返回上一层//前左指向前驱cp->left = prv;//left==prv即left指向prv所指向的结点//前驱非空 前结点的right指向后面那个结点if (prv)prv->right = cp;//更新prvprv = cp;//一路向右 遇空返回上一层InOrderConvert(cp->right, prv);}//==》当前层函数结束 返回上一层TreeNode* Convert(TreeNode* pRootOfTree){TreeNode* prev = nullptr;InOrderConvert(pRootOfTree, prev);TreeNode* head = pRootOfTree;//当传一颗空树 head在此就发挥了作用while (head && head->left)head = head->left;return head;}
};

2.数组:将二叉搜索树进行中序遍历可以得到由小到大的顺序排列

/*
struct TreeNode
{int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};
*/class Solution 
{
public:vector<TreeNode*> v;void inorder(TreeNode* root) {if (!root) return;inorder(root->left);v.push_back(root);inorder(root->right);}TreeNode* Convert(TreeNode* pRootOfTree) {if (!pRootOfTree) return pRootOfTree;inorder(pRootOfTree);for (int i = 0; i < v.size() - 1; i++) { v[i]->right = v[i + 1];v[i + 1]->left = v[i];}return v[0];}};

6.前序中序遍历序列构造二叉树

前序中序遍历序列构造二叉树
在这里插入图片描述

class Solution 
{
public:TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder, int& i, int begin, int end){if (begin > end) return nullptr;//遍历inorder 定位到根节点//[begin, x - 1] x [x + 1, end]int x = begin;for (x = begin; x <= end; ++x){if (inorder[x] == preorder[i])break;}TreeNode* root = new TreeNode(preorder[i++]);root->left = _buildTree(preorder, inorder, i, begin, x - 1);root->right = _buildTree(preorder, inorder, i, x + 1, end);return root;};TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder){int index = 0;//前序遍历数组第一个元素即根节点return _buildTree(preorder, inorder, index, 0, inorder.size() - 1);}
};

7.中序后序遍历序列构造二叉树

中序后序遍历序列构造二叉树
在这里插入图片描述

class Solution 
{
public:TreeNode* _buidTree(vector<int>& inorder, vector<int>& postorder, int& i,  int begin, int end){if (begin > end) return nullptr;int x = begin;for (x = begin; x <= end; ++x){if (inorder[x] == postorder[i])break;}TreeNode* root = new TreeNode(postorder[i--]);root->right = _buidTree(inorder, postorder, i, x + 1, end);root->left = _buidTree(inorder, postorder, i, begin, x - 1);return root;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {int index = postorder.size() - 1;return _buidTree(inorder, postorder, index, 0, inorder.size() - 1);}
};

8.二叉树的前序遍历【非递归】

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

vector<int> preorderTraversal(TreeNode* root)
{vector<int> v;       //v存储遍历的数据stack<TreeNode*> st; //利用栈的特点 调整读取数据的顺序存入到v中TreeNode* cp = root;while (cp || !st.empty()){//左路结点while (cp){v.push_back(cp->val);st.push(cp);cp = cp->left;}//左路结点的右子树TreeNode* top = st.top();cp = top->right;st.pop();}return v;
}

9.二叉树的中序遍历【非递归】

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

vector<int> inorderTraversal(TreeNode* root) 
{vector<int> v;stack<TreeNode*> st;TreeNode* cp = root;while (cp || !st.empty())   {while (cp){st.push(cp);cp = cp->left;}TreeNode* top = st.top();v.push_back(top->val);cp = top->right;st.pop();}return v;
};

10.二叉树的后序遍历【非递归】

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

1.法一:栈模拟实现递归

vector<int> postorderTraversal(TreeNode* root)
{vector<int> v;stack<TreeNode*> st;TreeNode* cp = root;TreeNode* prv = nullptr;while (cp || !st.empty()){while (cp){st.push(cp);cp = cp->left;}TreeNode* top = st.top();if (top->right == nullptr || top->right == prv){v.push_back(top->val);prv = top;st.pop();}else{cp = top->right;}}return v;
};

2.法二:前序遍历修改

class Solution 
{
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> v;stack<TreeNode*> st;st.push(root);while (!st.empty()){TreeNode* top = st.top();st.pop();if (top)v.push_back(top->val);elsecontinue;st.push(top->left);st.push(top->right);}reverse(v.begin(), v.end());return v;}
};

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

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

相关文章

Acwing 828. 模拟栈

Acwing 828. 模拟栈 题目要求思路讲解代码展示 题目要求 思路讲解 栈&#xff1a;先进后出 队列&#xff1a;先进先出 代码展示 #include <iostream>using namespace std;const int N 100010;int m; int stk[N], tt;int main() {cin >> m;while (m -- ){string o…

java创建excel文件和解析excel文件

创建excel文件 package com.bjpowernode.crm.poi;import org.apache.poi.hssf.usermodel.*; import org.apache.poi.ss.usermodel.HorizontalAlignment;import java.io.FileNotFoundException; import java.io.FileOutputStream; import java.io.IOException; import java.io.…

leetcode刷题(简单篇):9.回文数

9.回文数 题目描述&#xff1a;给你一个整数 x &#xff0c;如果 x 是一个回文整数&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 回文数是指正序&#xff08;从左向右&#xff09;和倒序&#xff08;从右向左&#xff09;读都是一样的整数。 例如&…

mybatis mapper.xml转建表语句

从网上下载了代码&#xff0c;但是发现没有DDL建表语句&#xff0c;只能自己手动创建了&#xff0c;感觉太麻烦&#xff0c;就写了一个工具类 将所有的mapper.xml放入到一个文件夹中&#xff0c;程序会自动读取生成建表语句 依赖的jar <dependency><groupId>org.d…

关于Python数据分析,这里有一条高效的学习路径

无处不在的数据分析 谷歌的数据分析可以预测一个地区即将爆发的流感&#xff0c;从而进行针对性的预防&#xff1b;淘宝可以根据你浏览和消费的数据进行分析&#xff0c;为你精准推荐商品&#xff1b;口碑极好的网易云音乐&#xff0c;通过其相似性算法&#xff0c;为不同的人…

Python中Mock和Patch的区别

前言&#xff1a; 嗨喽~大家好呀&#xff0c;这里是魔王呐 ❤ ~! python更多源码/资料/解答/教程等 点击此处跳转文末名片免费获取 在测试并行开发&#xff08;TPD&#xff09;中&#xff0c;代码开发是第一位的。 尽管如此&#xff0c;我们还是要写出开发的测试&#xff0c…

教育领域数据可视化:点亮知识之路

教育领域一直以来都在不断进步和演变&#xff0c;而数据可视化技术正在为这一领域带来一场革命。在过去的几年里&#xff0c;教育者们越来越意识到&#xff0c;通过将教育数据转化为可视化图表和图形&#xff0c;可以更好地理解学生的表现、需求和趋势&#xff0c;从而提供更好…

科学计算器网站Desmos网站

科学计算器网站Desmos网站 有时在学习工作或者生活中&#xff0c;需要用到计算问题&#xff0c;但由于电脑上没有安装相应的专业软件&#xff0c;难以计算有的问题&#xff0c;因而&#xff0c;本文推荐一种免费的在线计算网站Desmos。 一、Desmos网址 Desmos官网的地址为&a…

doccano 文本标注工具使用

最近在做面向大模型的文本标注工作&#xff0c;涉及到多人协同的问题&#xff0c;因此用到了doccano工具。 这个工具可以使用docker进行安装&#xff0c;安装之后的启动也都比较简单。 关于基础使用&#xff08;例如管理员登录、新建任务、上传数据集等&#xff09;&#xff…

系统架构设计师(第二版)学习笔记----信息系统基础

【原文链接】系统架构设计师&#xff08;第二版&#xff09;学习笔记----信息系统基础 文章目录 一、信息系统概述1.1 信息系统的5个基本功能1.2 信息系统发展阶段1.3 初始阶段的主要特点1.4 传播阶段的主要特点1.5 控制阶段的主要特点1.6 集成阶段的主要特点1.7 信息系统的种类…

计算机是如何工作的(上篇)

计算机发展史 世界上很多的高科技发明,来自于军事领域 计算机最初是用来计算弹道导弹轨迹的 弹道导弹 ~~国之重器,非常重要 两弹一星 原子弹,氢弹,卫星(背后的火箭发射技术) 计算弹道导弹轨迹的计算过程非常复杂,计算量也很大 ~~ 但是可以手动计算出来的(当年我国研究两弹一…

MySQL架构介绍与说明

1、MySQL架构介绍 和其它数据库相比&#xff0c;MySQL有点与众不同&#xff0c;它的架构可以在多种不同场景中应用并发挥良好作用。主要体现在存储引擎的架构上&#xff0c; 插件式的存储引擎架构将查询处理和其它的系统任务以及数据的存储提取相分离。这种架构可以根据业务的…

【数据结构】C++实现二叉搜索树

二叉搜索树的概念 二叉搜索树又称为二叉排序树&#xff0c;它或者是一棵空树&#xff0c;或者是具有以下性质的二叉树&#xff1a; 若它的左子树不为空&#xff0c;则左子树上所有结点的值都小于根结点的值。若它的右子树不为空&#xff0c;则右子树上所有结点的值都大于根结…

Spring Boot 动态加载jar文件

Spring Boot 动态加载jar文件 接口实现&#xff1a; package org.bc.device;public interface IDeviceHandler {String start();String stop(); }实现类&#xff1a; package org.bc.device; public class MqttDevice implements IDeviceHandler{ Override public String s…

Linux——Shell脚本编程(2)

一、Shell变量 Linux Shell 中的变量分为&#xff0c;系统变量 和 用户自定义变量 (这个用的比较多)。 系统变量 : $HOME、$PWD、$SHELL、$USER 等等&#xff0c;比如 : echo $HOME 等等.. 显示当前shell中所有变量 : set 举例说明&#xff1a; 二、设置环境变量 记得在注释…

小丑未能阻止抢购iPhone15,预约人数快500万了,而且越贵越买

iPhone15发布后&#xff0c;在昨天开启预约&#xff0c;从某电商平台可以看到预约人数已近300万&#xff0c;加上其他平台&#xff0c;估计预约人数已快500万了&#xff0c;显示出消费者仍然是嘴上说不爱&#xff0c;行动上却是迅速抢购&#xff0c;苹果的真香定律让竞争对手很…

服务器数据恢复-热备盘同步过程中硬盘离线的RAID5数据恢复案例

服务器数据恢复环境&#xff1a; 华为OceanStor某型号存储&#xff0c;11块硬盘组建了一组RAID5阵列&#xff0c;另外1块硬盘作为热备盘使用。基于RAID5阵列的LUN分配给linux系统使用&#xff0c;存放Oracle数据库。 服务器故障&#xff1a; RAID5阵列1块硬盘由于未知原因离线…

postgresql 内核源码分析 btree索引插入分析,索引页面分裂流程,多举措进行并发优化,对异常进行保护处理

Btree索引插入流程分析 ​专栏内容&#xff1a; postgresql内核源码分析手写数据库toadb并发编程 ​开源贡献&#xff1a; toadb开源库 个人主页&#xff1a;我的主页 管理社区&#xff1a;开源数据库 座右铭&#xff1a;天行健&#xff0c;君子以自强不息&#xff1b;地势坤&a…

HCIE-HCS规划设计搭建

1、相关术语 1、等价路由 等价路由&#xff08;Equal-cost routing&#xff09;是一种网络路由策略&#xff0c;用于在网络中选择多个具有相同路由度量&#xff08;路由距离或成本&#xff09;的最佳路径之一来转发数据流量。 当存在多个路径具有相同的路由度量时&#xff0c;…

VS Code 安装方法

1.安装控制台程序.NET SDK 功能&#xff1a;应用能够正常的运行和构建。 .NET SDK下载地址&#xff1a;下载 .NET(Linux、macOS 和 Windows) 2.安装驱动编辑器vscode vscode下载地址&#xff1a;https://code.visualstudio.com/Download 选择System Installer&#xff0c;…