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

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

文章目录

  • 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;}
};

相关文章:

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

文章目录 1.根据二叉树创建字符串2. 二叉树的层序遍历3.二叉树的层序遍历Ⅱ4.二叉树的最近公共祖先1.法一&#xff1a;定位p、q在左还是右 分类讨论2.法二&#xff1a;利用stack求出p、q路径 求相交值 5.二叉搜索树与双向链表1.法一&#xff1a;递归&#xff1a;递归过程修正指…...

docker系列(1) - docker环境篇

文章目录 1. docker环境1.1 docker安装1.2 阿里云镜像加速器1.2 docker管理工具(portainer)1.3 docker网络1.3.1 网络说明1.3.2 创建指定网关的网络 1. docker环境 1.1 docker安装 #CentOS 6 rpm -iUvh http://dl.fedoraproject.org/pub/epel/6/x86_64/epel-release-6-8.noar…...

web安全漏洞-SQL注入攻击实验

实验目的 学习sql显注的漏洞判断原理掌握sqlmap工具的使用分析SQL注入漏洞的成因 实验工具 sqlmap是用python写的开源的测试框架&#xff0c;支持MySQL&#xff0c;Oracle&#xff0c;PostgreSQL&#xff0c;Microsoft SQL Server&#xff0c;Microsoft Access&#xff0c;I…...

直接插入排序(C++实现)

文章目录 1. 基础概念&#x1f351; 内部排序和外部排序 2. 直接插入排序3. 动图演示4. 代码实现5. 性能分析 无论是日常生活还是很多科学领域当中&#xff0c;排序都是会经常面对的问题&#xff0c;比如按成绩对学校的学生排序&#xff0c;按薪水多少对公司员工排序等。 根据…...

【k8s】Pod 的钩子

Kubernetes&#xff08;K8s&#xff09;中的 Pod 可以使用以下几种勾子&#xff08;钩子&#xff09;来执行在容器生命周期的不同阶段运行的操作&#xff1a; PostStart&#xff08;启动后&#xff09;&#xff1a;该勾子在容器启动之后立即运行。它可以用于在容器内执行一些初…...

MCU软核 3. Xilinx Artix7上运行cortex-m3软核

0. 环境 - win10 vivado 2018.3 keil mdk - jlink - XC7A35TV12 1. 下载资料 https://keilpack.azureedge.net/pack/Keil.V2M-MPS2_DSx_BSP.1.1.0.pack https://gitee.com/whik/cortex_m3_on_xc7a100t 2. vivado 2018 Create Project -> Next -> -> Project n…...

基于SpringbootShiro实现的CAS单点登录

概述 单点登录&#xff08;Single Sign On,SSO&#xff09;是一种登录管理机制&#xff0c;主要用于多系统集成&#xff0c;即在多个系统中&#xff0c;用户只需要到一个中央服务器登录一次即可访问这些系统中的任何一个&#xff0c;无须多次登录。常见的例子就是&#xff0c;…...

SocketTool V4.0 使用说明

TCP/UDP Socket 调 试 工 具 提 供 了 TCP Server,TCP Client,UDP Server,UDP Client,UDP Group 五种 Socket 调试方案。 下面是一份简要的使用流程&#xff1a; TCP 通信测试&#xff1a; 1) 创建 TCP Server 选中左方的 TCP Server, 然后点击 ”创建 ”按钮&#xff0c;软件弹…...

Jenkins结合allure生成测试报告

前言&#xff1a; 我们在做自动化测试的过程中最重要的肯定是报告的输出啦&#xff0c;最近几年allure可以说是最最主流报告展示工具啦。 一、服务端安装allure 在安装Jenkins的机器 安装allure&#xff0c;我们在Jenkins上能跑动前提是在对应服务器上代码能正常运行&#xf…...

【Linux】缓冲区/回车换行

1、缓冲区 C程序默认有输出缓冲区。数据输出时&#xff0c;被及时看到&#xff0c;是立马刷新了&#xff1b;如果没被看到&#xff0c;是被暂存在数据缓冲区中。fflush(stdout); 【强制刷新】\n【行刷新&#xff0c;也是一种刷新方式】 2、回车换行 \n【回车换行】输入完一行内…...

Java手写插入排序和算法案例拓展

1. Java手写插入排序和算法案例拓展 1.1 算法思维导图 #mermaid-svg-jIZ3LAdg1NLcOvaM {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-jIZ3LAdg1NLcOvaM .error-icon{fill:#552222;}#mermaid-svg-jIZ3LAdg1NLcOvaM…...

Python Opencv实践 - 视频文件操作

参考资料&#xff1a; 视频处理VideoCapture类---OpenCV-Python开发指南&#xff08;38&#xff09;_python opencv videocapture_李元静的博客-CSDN博客 OpenCV VideoCapture.get()参数详解 - 简书FOURCC四字符码对照表_4fvcc_Kellybook的博客-CSDN博客 import cv2 as cv im…...

HCS 中的一些概念(二)

一、Service OM 1、首页&#xff08;资源状态&#xff09; 2、服务列表 计算资源&#xff1a;计算资源又分为可用分区&#xff08;AZ&#xff09;、规格和虚拟机组&#xff0c;可在此处创建虚拟机、虚拟机组、主机组和规格 网络资源&#xff1a;网络资源又分为物理网络…...

Scanner类用法(学习笔记)

Scanner类用法&#xff08;学习笔记&#xff0c;后续会补充&#xff09; 1.next&#xff08;&#xff09;用法 package com.yushifu.scanner; import java.util.Scanner;//util java工具包 //Scanner类&#xff08;获取用户的输入&#xff09; Scanner s new Scanner&#…...

idea2021.1.3版本双击启动,没反应

今天打开电脑&#xff0c;点开idea&#xff0c;界面悬在这里&#xff0c;几秒然后就是没了。然后就一直打不开idea了。 然后又是卸载重装&#xff0c;又是删除缓存文件。我把电脑关于idea的文件全都删除了 。重新安装后&#xff08;首次运行倒是可以打开&#xff0c;但是关掉id…...

MC-4/11/01/400 ELAU 软件允许用户完全访问相机设置

MC-4/11/01/400 ELAU 软件允许用户完全访问相机设置 一个完整的Sentinel模具保护解决方案包括一到四台冲击式摄像机、专用红外LED照明和镜头、Sentinel软件以及所有与模压机连接的必要互连组件。摄像机支架基于磁性&#xff0c;可快速、安全、灵活地部署。此外&#xff0c;一个…...

Error contacting service. It is probably not running.问题解决

一 问题描述 Error contacting service. It is probably not running. 查看zookeeper 目录下数据目录下的zookeeper.out 如果你没找到这个目录那么 OK 你的问题就是 zoo.cfg 文件中数据目录设置错误 zookeeper.out下报错 ERROR [main:QuorumPeerMain86] - Invalid config,…...

01_网络编程_传统IO

网络编程 1.什么是网络编程 在网络通信协议下&#xff0c;不同计算机上运行的程序&#xff0c;进行的数据传输。 如果想把一个计算的结果&#xff0c;或者是电脑上的文件通过网络传递给你的朋友&#xff0c;就需要用到网络编程。 在实际生活中&#xff0c;网络通信无处不在…...

vue 检查指定路由是否存在

今天路由跳转报错了 RangeError: Maximum call stack size exceeded 但显然 我的代码只有一个简单的路由跳转 并没有很大的的堆栈数据操作 所以 我就联想到了 会不会是因为路由不存在 我们可以通过 console.log(this.$router.options.routes)输出整个路由对象类看一下 或者…...

自动化办公更简单了:新版python-office,有哪些更新?

#职场经验谈# 大家好&#xff0c;这里是程序员晚枫&#xff0c;小破站/小红薯都叫这个名。 去年4月开源了一个Python自动化办公项目&#xff1a;python-office&#xff0c;GitHub和Gitee都能看到。1行代码实现复杂的自动化办公任务&#xff0c;帮助不懂代码的小白&#xff0c;…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理

引言 Bitmap&#xff08;位图&#xff09;是Android应用内存占用的“头号杀手”。一张1080P&#xff08;1920x1080&#xff09;的图片以ARGB_8888格式加载时&#xff0c;内存占用高达8MB&#xff08;192010804字节&#xff09;。据统计&#xff0c;超过60%的应用OOM崩溃与Bitm…...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)

Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败&#xff0c;具体原因是客户端发送了密码认证请求&#xff0c;但Redis服务器未设置密码 1.为Redis设置密码&#xff08;匹配客户端配置&#xff09; 步骤&#xff1a; 1&#xff09;.修…...

Maven 概述、安装、配置、仓库、私服详解

目录 1、Maven 概述 1.1 Maven 的定义 1.2 Maven 解决的问题 1.3 Maven 的核心特性与优势 2、Maven 安装 2.1 下载 Maven 2.2 安装配置 Maven 2.3 测试安装 2.4 修改 Maven 本地仓库的默认路径 3、Maven 配置 3.1 配置本地仓库 3.2 配置 JDK 3.3 IDEA 配置本地 Ma…...

C# 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

Yolov8 目标检测蒸馏学习记录

yolov8系列模型蒸馏基本流程&#xff0c;代码下载&#xff1a;这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中&#xff0c;**知识蒸馏&#xff08;Knowledge Distillation&#xff09;**被广泛应用&#xff0c;作为提升模型…...