当前位置: 首页 > 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…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

HDFS分布式存储 zookeeper

hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架&#xff0c;允许使用简单的变成模型跨计算机对大型集群进行分布式处理&#xff08;1.海量的数据存储 2.海量数据的计算&#xff09;Hadoop核心组件 hdfs&#xff08;分布式文件存储系统&#xff09;&a…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...

C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)

名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...

Caliper 配置文件解析:fisco-bcos.json

config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...

SpringAI实战:ChatModel智能对话全解

一、引言&#xff1a;Spring AI 与 Chat Model 的核心价值 &#x1f680; 在 Java 生态中集成大模型能力&#xff0c;Spring AI 提供了高效的解决方案 &#x1f916;。其中 Chat Model 作为核心交互组件&#xff0c;通过标准化接口简化了与大语言模型&#xff08;LLM&#xff0…...

【Linux】Linux安装并配置RabbitMQ

目录 1. 安装 Erlang 2. 安装 RabbitMQ 2.1.添加 RabbitMQ 仓库 2.2.安装 RabbitMQ 3.配置 3.1.启动和管理服务 4. 访问管理界面 5.安装问题 6.修改密码 7.修改端口 7.1.找到文件 7.2.修改文件 1. 安装 Erlang 由于 RabbitMQ 是用 Erlang 编写的&#xff0c;需要先安…...

深入理解 React 样式方案

React 的样式方案较多,在应用开发初期,开发者需要根据项目业务具体情况选择对应样式方案。React 样式方案主要有: 1. 内联样式 2. module css 3. css in js 4. tailwind css 这些方案中,均有各自的优势和缺点。 1. 方案优劣势 1. 内联样式: 简单直观,适合动态样式和…...

vxe-table vue 表格复选框多选数据,实现快捷键 Shift 批量选择功能

vxe-table vue 表格复选框多选数据&#xff0c;实现快捷键 Shift 批量选择功能 查看官网&#xff1a;https://vxetable.cn 效果 代码 通过 checkbox-config.isShift 启用批量选中,启用后按住快捷键和鼠标批量选取 <template><div><vxe-grid v-bind"gri…...

LeetCode - 148. 排序链表

目录 题目 思路 基本情况检查 复杂度分析 执行示例 读者可能出的错误 正确的写法 题目 148. 排序链表 - 力扣&#xff08;LeetCode&#xff09; 思路 链表归并排序采用"分治"的策略&#xff0c;主要分为三个步骤&#xff1a; 分割&#xff1a;将链表从中间…...