每日一题：LeetCode-105.从前序遍历与中序遍历构造二叉树-阿里云开发者社区

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

2023-11-30 16

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 每日一题：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;
    }
};

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

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

每日一题系列（day 02）

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

热门文章

最新文章

相关电子书