每日一题:LeetCode-105.从前序遍历与中序遍历构造二叉树

简介: 每日一题:LeetCode-105.从前序遍历与中序遍历构造二叉树

每日一题系列(day 02)

前言:

🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈

   🔎🔎如果说代码有灵魂,那么它的灵魂一定是👉👉算法👈👈,因此,想要写出💚优美的程序💚,核心算法是必不可少的,少年,你渴望力量吗😆😆,想掌握程序的灵魂吗❓❗️那么就必须踏上这样一条漫长的道路🏇🏇,我们要做的,就是斩妖除魔💥💥,打怪升级!💪💪当然切记不可😈走火入魔😈,每日打怪,日日累积,终能成圣🙏🙏!今天就开启我们的斩妖之旅!✈️✈️

LeetCode-105.从前序与中序遍历序列构成二叉树:

题目:

给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。

示例1:

示例2:

注意事项:

  • 1 <= preorder.length <= 3000
  • inorder.length == preorder.length
  • -3000 <= preorder[i], inorder[i] <= 3000
  • preorder 和 inorder 均 无重复 元素
  • inorder 均出现在 preorder
  • preorder 保证 为二叉树的前序遍历序列
  • inorder 保证 为二叉树的中序遍历序列

解法:

  思路:

  我们在学习二叉树的时候,很早就会了使用前序和中序或者中序和后序的序列来还原一颗二叉树。找到根节点位置将根节点创建出来,用左右子树接收根节点左右子树的前中序遍历的结果。接着向左子树和右子树分别重复上述操作,就可以递归构建一颗二叉树、

  1、我们把前序遍历数组的左右子树给找出来,所以需要中序遍历的结果来,用pos作为下标,只要中序遍历数组的值不等于前序遍历数组的第一个值,pos就++,最后得到的pos就是根节点。

  2、创建根节点,将前序遍历的第一个数组放入根节点。

  3、使用两个临时数组分别接收前序和中序遍历结果(pos是用来索引区间的下标),然后向左子树递归,递归完成之后将两个数组清空,同样,再用这两个数组接收右子树前序中序遍历的结果,将右子树递归处理,最后返回根节点即可。

  代码实现:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.size() == 0) return NULL;
        int pos = 0, n = preorder.size();//下标以及二叉树节点个数
        while(inorder[pos] != preorder[0]) pos++;//找出中序遍历根节点位置
        TreeNode *root = new TreeNode(preorder[0]);//创建根节点
        vector<int> preArr, inArr;//两个临时数组接收前序中序的遍历结果
        for(int i = 1; i <= pos; i++) preArr.push_back(preorder[i]);//将前序遍历结果给数组preArr
        for(int i = 0; i < pos; i++) inArr.push_back(inorder[i]);//将中序遍历结果给inArr
        root -> left = buildTree(preArr, inArr);//左子树递归
        preArr.clear();//清理两个临时数组
        inArr.clear();
        for(int i = pos + 1 ; i < n ; i++) preArr.push_back(preorder[i]);//同样的方法
        for(int i = pos + 1 ; i < n ; i++) inArr.push_back(inorder[i]);
        root -> right = buildTree(preArr, inArr);
        return root;
    }
};

  这是一道力扣的中等题,总的来说也并不算很难,理解掌握对前序遍历与中序遍历递归构建的过程才是最重要的。

相关文章
|
1月前
【LeetCode 43】236.二叉树的最近公共祖先
【LeetCode 43】236.二叉树的最近公共祖先
18 0
|
1月前
【LeetCode 38】617.合并二叉树
【LeetCode 38】617.合并二叉树
14 0
|
1月前
【LeetCode 37】106.从中序与后序遍历构造二叉树
【LeetCode 37】106.从中序与后序遍历构造二叉树
16 0
|
1月前
【LeetCode 34】257.二叉树的所有路径
【LeetCode 34】257.二叉树的所有路径
12 0
|
1月前
【LeetCode 32】111.二叉树的最小深度
【LeetCode 32】111.二叉树的最小深度
16 0
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
55 6
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
113 2
|
17天前
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
16 1
|
2月前
|
数据采集 负载均衡 安全
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口