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

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

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

目录

  • 【C++二叉树】进阶OJ题
      • 1.二叉树的层序遍历II
        • 示例代码
        • 解题思路
      • 2.二叉搜索树与双向链表
        • 示例代码
        • 解题思路
      • 3.从前序与中序遍历序列构造二叉树
        • 示例代码
        • 解题思路
      • 4.从中序与后序遍历序列构造二叉树
        • 示例代码
        • 解题思路
      • 5.二叉树的前序遍历(非递归迭代实现)
        • 示例代码
        • 解题思路
      • 6.二叉树的中序遍历(非递归迭代实现)
        • 示例代码
        • 解题思路
      • 7二叉树的后序遍历(非递归迭代实现)
        • 示例代码
        • 解题思路

作者:爱写代码的刚子

时间:2023.9.6

前言:本篇博客总结了一些二叉树有关的一些中等难度OJ题,总结这些题的解题思路


1.二叉树的层序遍历II

题目链接

示例代码

class Solution {
public:vector<vector<int>> levelOrderBottom(TreeNode* root) {vector<vector<int>> vv;if(!root){return vv;}queue<TreeNode*> q;q.push(root);while(!q.empty()){int curlevel = q.size();vv.push_back(vector<int> ());while(curlevel--){TreeNode *front=q.front();vv.back().push_back(front->val);q.pop();if(front->left){q.push(front->left);}if(front->right){q.push(front->right);}}}reverse(vv.begin(),vv.end());return vv;}
};

解题思路

  1. 选择使用队列来实现

  2. 在这里插入图片描述

  3. 注意这里使用变量curlevel来记录每层的元素个数,并且第二个while循环中需要curlevel来计数,因为题目中要求返回 vector<vector>,所以记录每层的元素个数是必要的。

  4. 由于题目要求返回自底向上的层序遍历,所以我们还需要reverse函数将vector<vector>容器进行反转。

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

题目链接

示例代码

class Solution {
public:void test(TreeNode* cur,TreeNode*& prev){if(cur==nullptr){return;}test(cur->left,prev);cur->left=prev;if(prev)//注意prev可能为nullptr{prev->right=cur;}prev=cur;test(cur->right,prev);}TreeNode* Convert(TreeNode* pRootOfTree) {TreeNode*prev=nullptr;test(pRootOfTree,prev);TreeNode* leftover=pRootOfTree;while(leftover&&leftover->left){leftover=leftover->left;}return leftover;}
};

解题思路

  1. 采用中序遍历
  2. 由于二叉树遍历的特殊性,我们无法找到下一个遍历的对象,所以我们设立新旧指针:cur和prev,由于根节点prev未知,所以我们传入nullptr
  3. 我们让cur指针先走,对旧节点的指针朝向进行修改(prev的left和right指针)
  4. 如图:在这里插入图片描述

本质其实就是让cur先走,记录先前节点(prev),并修改先前节点的指针朝向。

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

题目链接

示例代码

class Solution {
public:TreeNode* test(vector<int>& preorder, vector<int>& inorder,int begini,int& prei,int endi){if(begini>endi){return nullptr;}TreeNode* root=new TreeNode(preorder[prei]);int rooti=begini;while(rooti<=endi){if(preorder[prei]==inorder[rooti]){break;}else{++rooti;}}++prei;root->left=test(preorder, inorder,begini,prei,rooti-1);root->right=test(preorder, inorder,rooti+1,prei,endi);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int i=0;return test(preorder,inorder,0,i,preorder.size()-1);}
};

解题思路

  1. 前序遍历可以确定根节点的位置

  2. 确定了根再去中序遍历里找到对应的根

  3. 两者遍历的图示:在这里插入图片描述

  4. 观察图示结构,我们可以将前序遍历中的数据从左到右进行遍历,一次将遍历的节点作为根节点

  5. 观察图示结构,我们利用前序遍历中定的根节点在中序遍历中找到对应的位置,用中序遍历的结构来进行递归(类似分治)

  6. 递归的结束条件就是递归到子叶节点时,子叶节点再进行递归,递归区间有误。(begini>endi)

4.从中序与后序遍历序列构造二叉树

题目链接

示例代码

class Solution {
public:TreeNode*test(vector<int>& inorder, vector<int>& postorder,int begini,int& prei,int endi){if(begini>endi){return nullptr;}TreeNode*root=new TreeNode(postorder[prei]);int rooti=endi;while(rooti>=begini){if(inorder[rooti]==postorder[prei]){break;}--rooti;}--prei;root->right=test(inorder, postorder,rooti+1,prei,endi);root->left=test(inorder, postorder,begini,prei,rooti-1);//root->right=test(inorder, postorder,rooti+1,prei,endi);return root;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {int i=postorder.size()-1;return test(inorder, postorder,0,i,i);}
};

解题思路

  1. 思路与《从中序与后序遍历序列构造二叉树》类似,先画图:在这里插入图片描述

  2. 我们发现与《从中序与后序遍历序列构造二叉树》这道题中的结构类似,所以考虑后序遍历序列从右往左遍历,依次将访问的节点作为根节点

  3. 注意!后序遍历中访问完根节点后访问的是右节点,所以我们应先构造右子树,将《从中序与后序遍历序列构造二叉树》题中的示例代码中两个递归入口交换顺序即可

5.二叉树的前序遍历(非递归迭代实现)

题目链接

示例代码

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> v;stack<TreeNode*> st;TreeNode* tmp=root;while(tmp||!st.empty()){while(tmp){v.push_back(tmp->val);st.push(tmp);tmp=tmp->left;}tmp=st.top()->right;st.pop();}return v;}
};

解题思路

  1. 使用vector和stack
  2. 先将二叉树最左边的节点push进栈,将节点储存的值push_back进vector
  3. 再取出栈顶元素,控制指针进入栈顶元素节点的右子树,并pop该栈顶元素,重复以上步骤
  4. 图示:在这里插入图片描述

6.二叉树的中序遍历(非递归迭代实现)

题目链接

示例代码

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

解题思路

过程与前序遍历类似,只是访问的时机不同,中序遍历要在所有左子树push进栈后再进行访问,并pop栈顶元素

7二叉树的后序遍历(非递归迭代实现)

题目链接

示例代码

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

解题思路

  1. 我们需要设定访问时机,当右子树已经访问完了或者没有右子树时进行访问。
  2. 如何判读右子树是否访问完了:要引入prev指针记录上一个访问的节点,判断prev是否等于当前节点(top)的右子树。
  3. 注意这里使用的是if…else语句,并不是无脑cur=top->right

相关文章:

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

【C二叉树】进阶OJ题 目录 【C二叉树】进阶OJ题1.二叉树的层序遍历II示例代码解题思路 2.二叉搜索树与双向链表示例代码解题思路 3.从前序与中序遍历序列构造二叉树示例代码解题思路 4.从中序与后序遍历序列构造二叉树示例代码解题思路 5.二叉树的前序遍历&#xff08;非递归迭…...

C++——vector:resize与reserve的区别,验证写入4GB大数据时相比原生操作的效率提升

resize和reserve的区别 reserve&#xff1a;预留空间&#xff0c;但不实例化元素对象。所以在没有添加新的对象之前&#xff0c;不能引用容器内的元素。而要通过调用push_back或者insert。 resize&#xff1a;改变容器元素的数量&#xff0c;且会实例化对象&#xff08;指定或…...

基础配置xml

# 配置端口 server.port8081# 文件上传配置 # 是否支持文件上传 spring.servlet.multipart.enabledtrue # 是否支持文件写入磁盘 spring.servlet.multipart.file-size-threshold0 # 上传文件的临时目录 spring.servlet.multipart.locationd:/opt/tmp # 最大支持上传文件大小 sp…...

win环境安装SuperMap iserver和配置许可

SuperMap iServer是我国北京超图公司研发的基于跨平台GIS内核的云GIS应用服务器产品&#xff0c;通过服务的方式&#xff0c;面向网络客户端提供与专业GIS桌面产品相同功能的GIS服务&#xff0c;能够管理、发布多源服务&#xff0c;包括REST服务、OGC服务等。 SuperMap iserve…...

【Apollo学习笔记】——规划模块TASK之PIECEWISE_JERK_NONLINEAR_SPEED_OPTIMIZER(一)

文章目录 TASK系列解析文章前言PIECEWISE_JERK_NONLINEAR_SPEED_OPTIMIZER功能介绍PIECEWISE_JERK_NONLINEAR_SPEED_OPTIMIZER相关配置PIECEWISE_JERK_NONLINEAR_SPEED_OPTIMIZER流程确定优化变量定义目标函数定义约束ProcessSetUpStatesAndBoundsOptimizeByQPCheckSpeedLimitF…...

pytest parametrize多参数接口请求及展示中文响应数据

编写登陆接口 app.py from flask import Flask, request, jsonify, Responseapp Flask(__name__)app.route(/login, methods[POST]) def login():username request.form.get(username)password request.form.get(password)# 在这里编写你的登录验证逻辑if username admin…...

电视连续剧 ffmpeg 批量去掉片头片尾

思路&#xff1a; 一、用python获取每集的总时长 二、把每集的时间&#xff0c;拼接成想要的ffmpeg的剪切命令命令。 1、用python获取每集的总时长 1&#xff0c;安装moviepy库&#xff0c;直接安装太慢&#xff0c;换成国内的源 pip install moviepy -i http://mirrors.aliyu…...

二进制搭建kubernetes

二进制搭建kubernetes 一、常见的K8S部署方式1.Minikube2.Kubeadmin3.二进制安装部署 二、二进制搭建K8S(单台master)1.部署架构规划2.系统初始化配置3.部署 docker引擎4.部署 etcd 集群4.部署 Master 组件5.部署 Worker Node 组件6.部署网络组件 三、负载均衡部署1.配置load b…...

TDengine函数大全-系统函数

以下内容来自 TDengine 官方文档 及 GitHub 内容 。 以下所有示例基于 TDengine 3.1.0.3 TDengine函数大全 1.数学函数 2.字符串函数 3.转换函数 4.时间和日期函数 5.聚合函数 6.选择函数 7.时序数据库特有函数 8.系统函数 系统函数 TDengine函数大全DATABASECLIENT_VERSIONSE…...

北京互联网营销服务商浩希数字科技申请1350万美元纳斯达克IPO上市

来源&#xff1a;猛兽财经 作者&#xff1a;猛兽财经 猛兽财经获悉&#xff0c;总部位于北京的互联网营销服务商浩希数字科技&#xff08;Haoxi Health Technology Limited &#xff09;近期已向美国证券交易委员会&#xff08;SEC&#xff09;提交招股书&#xff0c;申请在纳斯…...

ElementUI浅尝辄止22:Alert 警告

用于页面中展示重要的提示信息。 常见于消息提示或警告框。 1.如何使用&#xff1f; 页面中的非浮层元素&#xff0c;不会自动消失。 //Alert 组件提供四种主题&#xff0c;由type属性指定&#xff0c;默认值为info。<template><el-alerttitle"成功提示的文案&…...

HCIP的mgre实验

题目 拓扑图 IP地址配置和缺省 R1 [r1]int g0/0/1 [r1-GigabitEthernet0/0/1]ip add 192.168.1.1 24 Aug 2 2023 20:38:20-08:00 r1 %%01IFNET/4/LINK_STATE(l)[0]:The line protocol IP on the interface GigabitEthernet0/0/1 has entered the UP state. [r1-GigabitEtherne…...

redis cluster集群搭建

集群搭建 启动6个redis实例 创建6份配置文件 mkdir redis-cluster cd redis-cluster mkdir 7001 7002 7003 8001 8002 80037001文件夹创建配置文件redis.conf port 7001 cluster-enabled yes cluster-config-file nodes-7001.conf cluster-node-timeout 5000 appendonly ye…...

小红书笔记爬虫

⭐️⭐️⭐️⭐️⭐️欢迎来到我的博客⭐️⭐️⭐️⭐️⭐️ &#x1f434;作者&#xff1a;秋无之地 &#x1f434;简介&#xff1a;CSDN爬虫、后端、大数据领域创作者。目前从事python爬虫、后端和大数据等相关工作&#xff0c;主要擅长领域有&#xff1a;爬虫、后端、大数据…...

国密GmSSL v2版本命令行方式生成国密sm2私钥、公钥、签名和验证签名

前言 GmSSL是国密算法的工具库&#xff08;主要包含SM2、SM3、SM4和国密SSL证书生成等功能&#xff09;&#xff0c;项目本身是OpenSSL的分支&#xff0c;但是截至文章发布为止&#xff0c;OpenSSL主分支的国密算法并不完善&#xff0c;目前并不支持签名和解签&#xff0c;所以…...

2023年9月惠州/深圳CPDA数据分析师认证找弘博创新

CPDA数据分析师认证是大数据方面的认证&#xff0c;助力数据分析人员打下扎实的数据分析基础知识功底&#xff0c;为入门数据分析保驾护航。 帮助数据分析人员掌握系统化的数据分析思维和方法论&#xff0c;提升工作效率和决策能力&#xff0c;遇到问题能够举一反三&#xff0c…...

it运维监控管理平台,统一运维监控管理平台

随着系统规模的不断扩大和复杂性的提高&#xff0c;IT运维管理的难度也在逐步增加。为了应对这一挑战&#xff0c;IT运维监控管理平台应运而生。本文将详细介绍IT运维监控管理平台的作用和优势以及如何选择合适的平台。 IT运维监控管理平台的作用管理平台 IT运维监控管理平台是…...

TDengine 官网换了新“皮肤”,来看看这个风格是不是你的菜

改版升级&#xff0c;不同以“网”&#xff01;为了更好地服务客户&#xff0c;让大家能够更便捷、清晰地了解我们的产品和功能&#xff0c;我们决定给 TDengine 官网换个新“皮肤”~精心筹备下&#xff0c;新官网终于成功与大家见面啦——https://www.taosdata.com/。TDengine…...

MFC:自绘CListBox,GetText返回一个乱码

问题描述 自绘CListBox&#xff0c;GetText返回一个乱码&#xff0c;并且还会伴随以下断言 解决方案 ListBox Control 属性【Has Strings】改为True即可...

shell 脚本发布前后端代码

shell 脚本发布前后端代码 1、发布前端2、发布后端 1、发布前端 #! /bin/bashif [ ! $1 ] thenecho "this command needs 1 parameters"exit fiif [ -d "/usr/local/nginx/html/xxxx-$1" ] thenecho "file exists: /usr/local/nginx/html/xxxx-$1, p…...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

React Native 导航系统实战(React Navigation)

导航系统实战&#xff08;React Navigation&#xff09; React Navigation 是 React Native 应用中最常用的导航库之一&#xff0c;它提供了多种导航模式&#xff0c;如堆栈导航&#xff08;Stack Navigator&#xff09;、标签导航&#xff08;Tab Navigator&#xff09;和抽屉…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战

“&#x1f916;手搓TuyaAI语音指令 &#x1f60d;秒变表情包大师&#xff0c;让萌系Otto机器人&#x1f525;玩出智能新花样&#xff01;开整&#xff01;” &#x1f916; Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制&#xff08;TuyaAI…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

Mysql8 忘记密码重置,以及问题解决

1.使用免密登录 找到配置MySQL文件&#xff0c;我的文件路径是/etc/mysql/my.cnf&#xff0c;有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

uniapp 字符包含的相关方法

在uniapp中&#xff0c;如果你想检查一个字符串是否包含另一个子字符串&#xff0c;你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的&#xff0c;但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...

Python 实现 Web 静态服务器(HTTP 协议)

目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1&#xff09;下载安装包2&#xff09;配置环境变量3&#xff09;安装镜像4&#xff09;node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1&#xff09;使用 http-server2&#xff09;详解 …...

如何通过git命令查看项目连接的仓库地址?

要通过 Git 命令查看项目连接的仓库地址&#xff0c;您可以使用以下几种方法&#xff1a; 1. 查看所有远程仓库地址 使用 git remote -v 命令&#xff0c;它会显示项目中配置的所有远程仓库及其对应的 URL&#xff1a; git remote -v输出示例&#xff1a; origin https://…...

CppCon 2015 学习:Simple, Extensible Pattern Matching in C++14

什么是 Pattern Matching&#xff08;模式匹配&#xff09; ❝ 模式匹配就是一种“描述式”的写法&#xff0c;不需要你手动判断、提取数据&#xff0c;而是直接描述你希望的数据结构是什么样子&#xff0c;系统自动判断并提取。❞ 你给的定义拆解&#xff1a; ✴ Instead of …...