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

2023-09-16 22:28:30

文章目录


在这里插入图片描述

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其中一个是根 那么根就为obj
		if (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为obj
		if ((pInLeft && qInRight) || (pInRight && qInLeft))
			return root;
		//均左==》递归到左子树
		if (pInLeft && qInLeft)
			return lowestCommonAncestor(root->left, p, q);
		//均右==》递归到右子树
		else
			return 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();
			else
				qRoute.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;
		//更新prv
		prv = 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);
			else
				continue;
			st.push(top->left);
			st.push(top->right);
		}
        reverse(v.begin(), v.end());
        return v;
    }
};
更多推荐

抖音矩阵系统源码：开发搭建

一、抖音矩阵系统源码开发概述抖音seo矩阵系统源码开发技术要求十分严格。首先，需要熟练掌握Python、Java等编程语言，具有扎实的算法基础。在此基础上，还需要具备深度学习、神经网络等相关技能，能够实现精准推荐和内容分析等功能。其次，抖音seo矩阵系统开发还需要专业的云计算技术支持，比如分布式计算、负载均衡等，以确保

智能配电房监控系统：实现配电智能化管理

智能配电房监控系统是一种基于现代信息技术，实现对配电房设备运行状态实时监控的智能化系统。它能够实时监测配电房设备的运行状态，及时发现设备故障，提高配电系统的可靠性，同时还可以实现远程监控和智能化控制，提高配电系统的效率。一、智能配电房监控系统的构成智能配电房监控系统主要由监控终端、通信网络和监控中心三部分构成。1.监控

ECharts

ECharts是一款基于JavaScript的数据可视化图表库，提供直观，生动，可交互，可个性化定制的数据可视化图表。ECharts提供了常规的折线图、柱状图、散点图、饼图、K线图，用于统计的盒形图，用于地理数据可视化的地图、热力图、线图，用于关系数据可视化的关系图、treemap、旭日图，多维数据可视化的平行坐标，还

Android 12 源码分析 —— 应用层 六（StatusBar的UI创建和初始化)

Android12源码分析——应用层六（StatusBar的UI创建和初始化)在前面的文章中,我们分别介绍了Layout整体布局,以及StatusBar类的初始化.前者介绍了整体上面的布局,后者介绍了三大窗口的创建的入口处,以及需要做的准备工作.现在我们分别来细化三大窗口的UI创建和初始化,首先从StatusBar窗口

【初阶数据结构】——堆排序和TopK问题

=========================================================================个人主页代码仓库C语言专栏初阶数据结构专栏Linux专栏===========================================================

在React中使用Immutable.js

Immutable的几种数据类型在React中使用Immutable.js实例扩展LodashLodash常用api分类Lodash中常用的API介绍：Lodash中api和javascript中api有什么不同react中如何使用LodashImmutable的几种数据类型List:有序索引集，类似JavaScrip

新版发布 | Cloudpods v3.10.5 和 v3.9.13 正式发布

Cloudpodsv3.10.5本期发布中，ocboot部署脚本有较多变化，首先支持以非root用户执行安装流程，其次响应社区的呼吁，增加了–stack参数，允许Allinone一键安装仅包含私有云（参数为edge）或云管（参数为cmp）的部署。本期亮点为KVM虚拟机对GPU的支持，不仅支持了虚拟机挂载图形模式的GPU

MacOS 控制固态磁盘写入量，设置定时任务监控

M1芯片的内存交换策略非常激进，导致内存较小的机型固态硬盘写入量十分恐怖，网上很多人都有类似的遭遇。如何看待8G256GM1MacBookAir使用一个月硬盘写入22TB+?而固态硬盘是有擦除、写入寿命的，一般就按100次算，256G大概就是250TB。当然，并不是说超过这个数，硬盘就坏了，只是一般超过这个数，再坏，厂

9.2 【MySQL】独立表空间结构

9.2.1区（extent）的概念对于16KB的页来说，连续的64个页就是一个区，也就是说一个区默认占用1MB空间大小。不论是系统表空间还是独立表空间，都可以看成是由若干个区组成的，每256个区被划分成一组。画个图表示就是这样：其中extent0~extent255这256个区算是第一个组，extent256~exte

Qt 数据库的注册和登录功能

widget.h#ifndefWIDGET_H#defineWIDGET_H#include<QPushButton>#include<QWidget>#include<QDebug>#include<QString>#include<QMessageBox>#include<QFile>#include"client

Linux下的第一个小程序——进度条

目录​编辑一，进度条的第一个版本1.准备工作2.写Makefile文件3.开始构建进度条1.process.h文件2.process.c文件3.main.c文件二，进度条的第二个版本1.为什么还要写第二个版本？2.如何升级？3.升级代码1.搭建场景一，进度条的第一个版本1.准备工作在写进度条之前，我们得把前期的准备工作

热文推荐
  1. Spark_Spark内存模型管理

    工作中经常用到Spark内存调参，之前还没对这块记录，这次记录一下。环境参数spark内存模型中会涉及到多个配置，这些配置由一些环境参数及其配置值有关，为防止后面理解混乱，现在这里列举出来，如果忘记了，可以返回来看看：spark.executor.memory：JVMOn-Heap内存（堆内内存），在使用sparksu

  2. 云服务器部署k8s集群

    在两台不同厂商的云服务器上部署k8s集群，遇到一些问题。在此进行下总结。首先要网络能够互通，我是通过添加虚拟网卡的方式lsmod|grepip_vs#检查是否有开启#临时开启ip_vsforiin$(ls/lib/modules/$(uname-r)/kernel/net/netfilter/ipvs|grep-o"^

  3. 【Spark】PySpark DataFrame

    1SparkSession执行环境入口2构建DataFrame2.1由rdd构建(StructType、StructField)2.2由pandas.DataFrame构建2.3由外部数据构建2.3.1text数据源2.3.2json数据源2.3.3csv数据源3DataFrame操作3.1SQL风格3.2DSL风格3

  4. WebGL HUD（平视显示器）

    目录HUD（平视显示器）如何实现HUD示例程序（HUD.html）示例程序（HUD.js）代码详解在网页文字上方显示三维物体代码详解HUD（平视显示器）平视显示器（headupdisplay）简称HUD，最早用于飞机驾驶。平视显示器将一些重要信息投射到飞机驾驶舱前方的一块玻璃上，飞行员能够将外界的影像和这些重要信息融合

  5. 使用vue-cli搭建SPA项目

    目录一、SPA项目构建及目录讲解1.1SPA定义1.2SPA优点1.3VueCLI定义1.4VueCLI功能解析1.5安装vue-cli1.6创建SPA项目1.7项目结构说明1.8项目结构说明1.8.1build文件夹1.8.2config文件夹1.8.3node_modules文件夹1.8.4src文件夹1.8.5s

  6. ctfshow web入门（2）

    web11打开这个网站，到网站诊断分析模块搜索域名web12提示有时候网站上的公开信息，就是管理员常用密码打开，就是个购物网站因为昨天刚做robots.txt我就搜了一下真的有，提示admin这个页面访问一下，username肯定是admin，但是密码。有点晕。但是看到提示我就又去看了看原来的页面，有没有可疑的密码在末

  7. MQTT服务器搭建

    本次搭建的MQTT服务器是emqx提供的服务器1、下载https://www.emqx.com/en/downloads/broker从官网下载5.2.0版本emqx-5.2.0-windows-amd64.zip下载完成直接安装2、配置，修改端口号mqtt默认端口号常规的用法，我们一般使用和开放这两个端口：1883，

  8. php生成随机验证码图片

    1，CaptchaPicture.php用于生成画布，然后在画布上生成四位随机验证码<?phpsession_start();header("Content-type:image/png");//创建图像的格式$image_width=76;//设置图像的宽度$image_height=40;//设置图像的高度$len

  9. 线性代数与编程语言结合 基础

    什么是线性代数线性代数是数学的一个分支，研究向量空间和线性变换的理论与方法。它涉及了向量、矩阵、线性方程组、线性映射等概念与运算规则。线性代数在科学和工程领域中被广泛应用，如物理学、计算机图形学、统计学、电子工程等。它提供了一种强大的工具和语言来描述和解决线性问题，比如矩阵求逆、解线性方程组、特征值和特征向量等。通过线