前序遍历+中序遍历重建二叉树

简介: 前序遍历+中序遍历重建二叉树

文章目录

  • 题目
  • AC代码


题目

本题链接:剑指 Offer 07. 重建二叉树

注:链接题目仅代表和本题大体相似

因为是考研笔试,本题代码以C语言去写


AC代码

代码解释:本题要求就是给定两个序列:分别为树的前序遍历和树的中序遍历,我们知道,在树的各节点值均不同的情况下,给定一个树的💘前序遍历+中序遍历💘 || 💘后序遍历+中序遍历💘 || 💘层序遍历+中序遍历💘,可以唯一确定出一棵树,这里给出数据结构的相关推导过程:

2.jpg

3.jpg

4.jpg

5.jpg

⭐️上述笔记仅涉及重构二叉树的内容,如果想获得完整【数据结构】树与二叉树的相关笔记请访问博客:树与二叉树 (还未超链接,约12.20日完成超链接)

从上述中我们可以看出,其实重建二叉树可以不断的通过递归去实现,递归划分左右子树的点(根节点)就是就在于在中序遍历中找到这个点,这就是我们下述代码中for循环实现的东西:

int i;
for (i = 0; i < inorder_size; i ++ ){
  if (root -> val == inorder[i]) 
    break;
}


⭐️当然这一步我们可以用哈希表去写,这样时间复杂度会降到O(n),C++可直接调用哈希函数:STL—map,当然我们在做笔试题的时候是不允许调用函数的,我们也可以手写哈希函数:哈希表,读者可以根据我写的哈希表这个博客去优化改进下述代码,对于考研笔试而言,写成我写的下述代码就已经足够了,并不要求掌握手写哈希函数


代码:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* buildTree(int* preorder, int preorder_size, int* inorder, int inorder_size) {
    if (preorder == NULL || preorder_size == 0 || inorder == NULL || inorder_size == 0){
        return NULL;
    }
    struct TreeNode *root = (struct TreeNode*)malloc(sizeof (struct TreeNode));
    root -> val = preorder[0];
    int i;
    for (i = 0; i < inorder_size; i ++ ){
        if (root -> val == inorder[i]) 
            break;
    }
    root -> left = buildTree(&preorder[1], i, &inorder[0], i);
    root -> right = buildTree(&preorder[i + 1], preorder_size - i - 1, &inorder[i + 1], inorder_size - i - 1);
    return root;
}


目录
相关文章
|
Prometheus Cloud Native Unix
完全解读Prometheus查询(上)
完全解读Prometheus查询(上)
372 0
|
安全 测试技术 Linux
安装配置Samba服务器(CentOS7)
假设我们有这样一个需求 共享名     路径         权限 Mealkey_Share   /smb/docs    所有人员包括来宾均可以访问 Group     /smb/tech    仅允许特定组的用户进行读写访问   特定组的组名为RD,目前的有zyy一人...
4381 0
|
9月前
|
C#
【Azure Function】Function App出现System.IO.FileNotFoundException异常
Exception while executing function: xxxxxxx,The type initializer for 'xxxxxx.Storage.Adls2.StoreDataLakeGen2Reading' threw an exception. Could not load file or assembly 'Microsoft.Extensions.Configuration, Version=9.0.0.0, Culture=neutral, PublicKeyToken=adb9793829ddae60'. The system cannot find the
204 64
|
机器学习/深度学习 数据采集 算法
Python实现贝叶斯岭回归模型(BayesianRidge算法)并使用K折交叉验证进行模型评估项目实战
Python实现贝叶斯岭回归模型(BayesianRidge算法)并使用K折交叉验证进行模型评估项目实战
|
消息中间件 Java 中间件
微服务技术系列教程(32) - SpringCloud-消息总线
微服务技术系列教程(32) - SpringCloud-消息总线
188 0
|
JavaScript Java 测试技术
基于springboot+vue.js+uniapp小程序的产品售后管理系统附带文章源码部署视频讲解等
基于springboot+vue.js+uniapp小程序的产品售后管理系统附带文章源码部署视频讲解等
144 5
基于springboot+vue.js+uniapp小程序的产品售后管理系统附带文章源码部署视频讲解等
|
存储 缓存 Kubernetes
harbor 部署入门指南(1)
harbor 部署入门指南(1)
harbor 部署入门指南(1)
|
传感器 机器学习/深度学习 自动驾驶
初识自动驾驶技术之旅 第一课 学习笔记
感谢大家收听今天的课程介绍,我非常荣幸地能在这里向大家介绍一位百度Apollo开源平台首席架构师胡旷老师, 作为首席架构师,胡旷老师在自动驾驶领域的研究和应用方面做出了重要贡献。他专注于自动驾驶系统的开发和优化,研究高精度感知、决策与规划、传感器融合等关键技术,并致力于将自动驾驶落地应用于城市交通等领域,相信与他的学习过程将给您带来更多的惊喜和收获。
|
缓存 IDE Oracle
Linux 磁盘I/O读写速度检测
Linux 磁盘I/O读写速度检测
416 0