从前序与中序遍历序列构造二叉树1
![star](https://csdnimg.cn/release/downloadcmsfe/public/img/star.98a08eaa.png)
![preview](https://dl-preview.csdnimg.cn/86284314/0001-9c1a0a5926d166f35821d780dd72137c_thumbnail.jpeg)
![preview-icon](https://csdnimg.cn/release/downloadcmsfe/public/img/scale.ab9e0183.png)
从前序与中序遍历序列构造二叉树 从前序与中序遍历序列构造二叉树是 LeetCode 中的一道经典题目,该问题要求根据一棵树的前序遍历和中序遍历构造二叉树。为了解决这个问题,我们需要了解二叉树的基本概念和遍历方式。 二叉树的基本概念 二叉树是一种特殊的树形数据结构,它的每个节点最多有两个子节点:左子节点和右子节点。每个节点包含一个值和两个指针,分别指向左子节点和右子节点。二叉树可以用来存储和组织大量的数据,並且可以使用遍历算法来遍历和访问树中的节点。 前序遍历和中序遍历 前序遍历和中序遍历是二叉树的两种常见遍历方式: * 前序遍历:先访问当前节点,然后递归地访问左子节点和右子节点。遍历顺序为:根节点 -> 左子树 -> 右子树。 * 中序遍历:先递归地访问左子节点,然后访问当前节点,最后递归地访问右子节点。遍历顺序为:左子树 -> 根节点 -> 右子树。 构造二叉树的算法 为了从前序遍历和中序遍历序列构造二叉树,我们可以使用递归算法。该算法的主要思想是: 1. 首先,从前序遍历序列中取出当前节点的值,并创建一个新的树节点。 2. 然后,在中序遍历序列中找到当前节点的索引,并将其分为左子树和右子树两部分。 3. 递归地构造左子树和右子树,并将其连接到当前节点上。 以下是该算法的 C++ 实现代码: ```cpp class Solution { public: TreeNode* _build(vector<int>& preorder, vector<int>& inorder,int& preidx,int start,int end) { if(start > end) return nullptr; TreeNode* cur = new TreeNode(preorder[preidx]); int curidx = start; for(; curidx <= end; curidx++) { if(inorder[curidx] == preorder[preidx]) break; // 找到分界点 curidx } if(start < curidx) { cur->left = _build(preorder, inorder, ++preidx, start, curidx-1); } else { cur->left = nullptr; } if(curidx < end) { cur->right = _build(preorder, inorder, ++preidx, curidx+1, end); } else { cur->right = nullptr; } return cur; } TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { int previdx = 0; return _build(preorder, inorder, previdx, 0, inorder.size()-1); } }; ``` 时间复杂度和空间复杂度 该算法的时间复杂度为 O(n),其中 n 是树中的节点个数。空间复杂度为 O(n),用于存储递归栈。 总结 从前序与中序遍历序列构造二叉树是 LeetCode 中的一道经典题目,该问题要求根据一棵树的前序遍历和中序遍历构造二叉树。为了解决这个问题,我们需要了解二叉树的基本概念和遍历方式,并使用递归算法来构造二叉树。
![](https://csdnimg.cn/release/download_crawler_static/86284314/bg1.jpg)
![md](https://img-home.csdnimg.cn/images/20210720083646.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![mp4](https://img-home.csdnimg.cn/images/20210720083504.png)
![md](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![application/x-zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![avatar](https://profile-avatar.csdnimg.cn/ea87570ee0334956af76dcdd79eb7c46_weixin_35735370.jpg!1)
- 粉丝: 21
- 资源: 344
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![voice](https://csdnimg.cn/release/downloadcmsfe/public/img/voice.245cc511.png)
![center-task](https://csdnimg.cn/release/downloadcmsfe/public/img/center-task.c2eda91a.png)
最新资源
- 网络爬虫软件研究与开发pdf
- Java项目-基于SSM+JSP的母婴用品网站的设计与实现(源码+数据库脚本+部署视频+代码讲解视频+全套软件)
- 基于微信小程序的购物商城app设计带Java后端+源代码+文档说明+数据库.zip
- 基于51单片机外设应用设计.DSN后缀PROTEUS仿真仿真源文件及C语言实例源码例程合集(300个).zip
- “Bunnies and Badgers”兔子和獾和是一个基于pygame库开发的射击游戏
- 华为打印机,华为打印机资料
- Java项目-基于SSM+JSP的医院门诊挂号系统的设计与实现(源码+数据库脚本+部署视频+代码讲解视频+全套软件)
- mac os button功能demo
- 如何在Ubuntu上安装软件?
- 华为HCIA-WLAN 3.0 课程视频(20 熟悉命令行.mp4)
![feedback](https://img-home.csdnimg.cn/images/20220527035711.png)
![feedback-tip](https://img-home.csdnimg.cn/images/20220527035111.png)
![dialog-icon](https://csdnimg.cn/release/downloadcmsfe/public/img/green-success.6a4acb44.png)
评论1