C++进阶--二叉树编程题

news/2024/3/29 18:18:01/文章来源:https://blog.csdn.net/CL2426/article/details/129224176

文章目录

    • 力扣606. 根据二叉树创建字符串
    • 力扣102. 二叉树的层序遍历
    • 力扣236. 二叉树的最近公共祖先
    • JZ36 二叉搜索树与双向链表
    • 力扣105--通过前序和中序遍历构造二叉树
    • 力扣144--二叉树的前序遍历(非递归)
    • 力扣94--二叉树的中序遍历(非递归)
    • 力扣145--二叉树的后序遍历(非递归)

力扣606. 根据二叉树创建字符串

题目链接:力扣606

在这里插入图片描述

class Solution {
public:void _tree2str(TreeNode* root, string& str){str += to_string(root->val);if(root->left){str += '(';_tree2str(root->left, str);str += ')';}if(root->left == nullptr && root->right){str += "(";str += ")";}if(root->right){str += '(';_tree2str(root->right, str);str += ')';}}string tree2str(TreeNode* root) {string str;_tree2str(root, str);return str;}
};

力扣102. 二叉树的层序遍历

力扣102
本质就是是一个广度优先搜索, — > 借助队列来完成。
在这里插入图片描述

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {if(root == nullptr)return vector<vector<int>>();queue<TreeNode*> q;q.push(root);vector<vector<int>> vv;while(!q.empty()){int sz = q.size();vector<int> v;while(sz--){TreeNode* node = q.front();q.pop();v.push_back(node->val);if(node->left)q.push(node->left);if(node->right)q.push(node->right);}vv.push_back(v);}return vv;}
};

力扣236. 二叉树的最近公共祖先

力扣236

在这里插入图片描述
解题思路 : 我们用一个函数 bool inTree(BTreeNode* root, BTreeNode* x) 去判断这个目标节点p, q是在root的那一侧,
如果都是在左侧, 则到root的左侧去找, 如果都在右侧, 那就到root的右侧去找。
另外的话, p 或者q是root的话, 直接返回root就行

class Solution {
public:bool inTree(TreeNode* root, TreeNode* x){if (root == nullptr)return false;if (root->val == x->val)return true;return inTree(root->left, x) || inTree(root->right, x);}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q){if (root == p || root == q)return root;bool pLeft = inTree(root->left, p), pRight = !pLeft;bool qLeft = inTree(root->left, q), qRight = !qLeft;if (pLeft && qLeft){return lowestCommonAncestor(root->left, p, q);}else if (pRight && qRight){return lowestCommonAncestor(root->right, p, q);}else{return root;}return nullptr;}
};

JZ36 二叉搜索树与双向链表

题目链接: 牛客JZ36

在这里插入图片描述

class Solution {
public:void _Convert(TreeNode* root, TreeNode*& pre)       //注意一下, 要传引用!!!!!{if(root == nullptr)return;_Convert(root->left, pre);root->left = pre;if(pre)pre->right = root;pre = root;_Convert(root->right, pre);}TreeNode* Convert(TreeNode* pRootOfTree) {if(pRootOfTree == nullptr)return nullptr;TreeNode* pre = nullptr;_Convert(pRootOfTree, pre);TreeNode* head = pRootOfTree;       //这个根节点肯定是在中间的, 通过向前找即可。while(head->left) head = head->left;return head;}
};

力扣105–通过前序和中序遍历构造二叉树

力扣105
核心思路 : 通过前序遍历找到根节点, pi是前序遍历的下标,
然后通过中序遍历确定左右子树的范围
根的下标rooti 左树的区间范围 [inbegin rooti-1] 右树的区间范围 : [rooti+1, inend]。

在这里插入图片描述

class Solution {
public:TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder, int& pi, int  inbegin, int inend){if(inend < inbegin)  //区间不存在的情况{return nullptr;        }TreeNode* root = new TreeNode(preorder[pi]);pi++;     int rooti = inbegin;    //找出根节点, 分出左,右子树。while(rooti <= inend){if(root->val != inorder[rooti])rooti++;elsebreak;}root->left = _buildTree(preorder, inorder, pi, inbegin, rooti-1);root->right = _buildTree(preorder, inorder, pi, rooti+1, inend);return root;} TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int pi = 0; // 前序遍历的下标return _buildTree(preorder, inorder, pi, 0, inorder.size() - 1);}
};

力扣144–二叉树的前序遍历(非递归)

力扣144

在这里插入图片描述

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

力扣94–二叉树的中序遍历(非递归)

力扣94
在这里插入图片描述

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

力扣145–二叉树的后序遍历(非递归)

力扣145

和前序遍历基本上一样。
前序遍历是 : 根, 左, 右
后序遍历是 : 左,右, 根

核心 : 将后序看出 根, 右, 左 – >最后的结果逆置即可。
我们只用先将右路节点入栈并且访问, 然后出栈的时候将左树节点的右路节点入栈。
然后循环, 最后逆置数组即可。

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

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

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

相关文章

虹科新闻|虹科与iX systems正式建立合作伙伴关系

近日&#xff0c;虹科与美国iXsystems公司达成战略合作&#xff0c;虹科正式成为iXsystems公司在中国区域的认证授权代理商。未来&#xff0c;虹科将携手iXsystems&#xff0c;共同致力于提供企业级存储解决方案。虹科及iXsystems双方的高层领导人员都对彼此的合作有很大的信心…

操作系统基础教程

目录 第二章&#xff1a;处理器管理 概览 进程调度的层次 进程的调度方式&#xff1a; 调度的评价标准&#xff1a; 典型的调度算法&#xff1a; 第三章&#xff1a;同步、通信和死锁 什么是进程同步&#xff1f; 什么是进程互斥&#xff1f; 进程同步的实现方式 进程…

JVM总结

1. 内存结构 线程私有区 程序计算器 作用&#xff1a;是一块较小的内存空间&#xff0c;存储的是当前线程所执行的字节码文件的序号特点&#xff1a;线程私有&#xff0c;不会出现内存空间溢出 虚拟机栈 虚拟机栈是管理JAVA方法执行的内存模型&#xff0c;每个方法执行时都…

贴吧顶贴软件《今日/更新》

贴吧顶贴软件《今日/更新》百收贴吧工具箱&#xff0c;贴吧顶帖软件&#xff0c;贴吧推广引流神器#贴吧顶帖#贴吧推广 hello&#xff0c;大家好&#xff0c;我是软件的作者百收编辑狂潮老师。本次的视频讲解是作为一个百度顶贴的自动化脚本的视频安装教程和使用教程。你作为新…

SpringCloud(五)MQ消息队列

MQ概念常见消息模型helloworld案例实现实现spring AMQP发送消息实现spring AMQP接收消息工作消息队列实现发布订阅模型Fanout Exchange实现DirectExchange实现TopicExchange实现DirectExchange 和FanoutExchange的差异DirectExchange 和TopicExchange的差异基于RabbitListener注…

钉钉产品体验报告

一、调研的目的了解企业社交软件&#xff0c;借写竞品分析来帮助自己整理思路&#xff0c;看清市场的发展趋势&#xff1b;体验这类企业设计软件&#xff0c;掌握产品核心业务流程和产品结构&#xff0c;把握需求对应的功能点和界面结构&#xff0c;并侧面了解用户习惯&#xf…

用Python做数据分析有哪些优势?

众所周知&#xff0c;可以用作数据分析的语言有很多&#xff0c;包含Python、R语言等&#xff0c;而且Python被誉为数据分析的一大利器&#xff0c;更是该领域的首选语言&#xff0c;那么用Python做数据分析有哪些优势呢?跟着蛋糕往下看。 第一、Python语言自身的优势 Pytho…

ShardingSphere水平、垂直分库、分表和公共表

目录一、ShardingSphere简介二、ShardingSphere-分库分表1、垂直拆分&#xff08;1&#xff09;垂直分库&#xff08;2&#xff09;垂直分表2、水平拆分&#xff08;1&#xff09;水平分库&#xff08;2&#xff09;水平分表三、水平分库操作1、创建数据库和表2、配置分片的规则…

BigGAN

1、BIGGAN 解读1.1、作者 Andrew Brock、Jeff Donahue、Karen Simonyan 1.2、摘要 尽管最近在生成图像建模方面取得了进展&#xff0c;但从 ImageNet 等复杂数据集中 成功生成高分辨率、多样化的样本仍然是一个难以实现的目标。为此&#xff0c;我们以迄 今为止最大的规模训练生…

fastadmin:在新增页面,打开弹窗单选,参数回传

样式&#xff1a;核心代码&#xff1a;一、弹窗的控制器中&#xff1a;// 定义一个公共函数select()&#xff0c;如果这个请求是Ajax&#xff0c;则返回index()函数&#xff0c;否则返回view对象的fetch()函数。 public function select() {if ($this->request->isAjax(…

【软件测试】测试老鸟的迷途,进军高级自动化测试测试......

目录&#xff1a;导读前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09;前言 很多从业几年的选手…

【阿旭机器学习实战】【37】电影推荐系统---基于矩阵分解

【阿旭机器学习实战】系列文章主要介绍机器学习的各种算法模型及其实战案例&#xff0c;欢迎点赞&#xff0c;关注共同学习交流。 电影推荐系统 目录电影推荐系统1. 问题介绍1.1推荐系统矩阵分解方法介绍1.2 数据集&#xff1a;ml-100k2. 推荐系统实现2.1 定义矩阵分解函数2.2 …

消息中间件的概念

中间件(middleware)是基础软件的一大类&#xff0c;属于可复用的软件范畴。中间件在操作系统软件&#xff0c;网络和数据库之上&#xff0c;应用软件之下&#xff0c;总的作用是为处于自己上层的应用软件提供运行于开发的环境&#xff0c;帮助用户灵活、高效的开发和集成复杂的…

ICA简介:独立成分分析

1. 简介 您是否曾经遇到过这样一种情况&#xff1a;您试图分析一个复杂且高度相关的数据集&#xff0c;却对信息量感到不知所措&#xff1f;这就是独立成分分析 (ICA) 的用武之地。ICA 是数据分析领域的一项强大技术&#xff0c;可让您分离和识别多元数据集中的底层独立来源。 …

PPP简介,PPP分层体系架构,PPP链路建立过程及PPP的帧格式

PPP&#xff08;Point-to-Point Protocol&#xff09;是一种用于在两个网络节点之间传输数据的通信协议。它最初是为在拨号网络上进行拨号连接而开发的&#xff0c;现在已经被广泛应用于各种网络环境中&#xff0c;例如在宽带接入、虚拟专用网&#xff08;VPN&#xff09;等场景…

【JAVA】一个项目如何预先加载数据?

这里写目录标题需求实现AutowiredPostConstruct实例CommandLineRunner实例ApplicationListener实例参考需求 一般我们可能会有一些在应用启动时加载资源的需求&#xff0c;局部或者全局使用&#xff0c;让我们来看看都有哪些方式实现。 实现 Autowired 如果是某个类里需求某…

[1]MyBatis+Spring+SpringMVC+SSM整合

一、MyBatis 1、MyBatis简介 1.1、MyBatis历史 MyBatis最初是Apache的一个开源项目iBatis, 2010年6月这个项目由Apache Software Foundation迁移到了Google Code。随着开发团队转投Google Code旗下&#xff0c; iBatis3.x正式更名为MyBatis。代码于2013年11月迁移到Github。…

Vue中如何利用websocket实现实时通讯

首先我们可以先做一个简单的例子来学习一下简单的websocket模拟聊天对话的功能 原理很简单&#xff0c;有点像VUE中的EventBus&#xff0c;用emit和on传来传去 首先我们可以先去自己去用node搭建一个本地服务器 步骤如下 1.新建一个app.js&#xff0c;然后创建pagejson.js文…

【Linux】-- POSIX信号量

目录 POSIX信号量 sem_init - 初始化信号量 sem_destroy - 销毁信号量 sem_wait - 等待信号量&#xff08;P操作&#xff09; 基于环形队列的生产消费模型 数据结构 - 环形结构 实现原理 POSIX信号量 #问&#xff1a;什么是信号量&#xff1f; 1. 共享资源 -> 任何一…

【笔记】两台1200PLC进行S7 通信(1)

使用两台1200系列PLC进行S7通信&#xff08;入门&#xff09; 文章目录 目录 文章目录 前言 一、通信 1.概念 2.PLC通信 1.串口 2.网口 …