每日一題系列（day 02）

前言：

?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ??

?? ????如果說代碼有靈魂，那么它的靈魂一定是????算法????，因此，想要寫出??優(yōu)美的程序??，核心算法是必不可少的，少年，你渴望力量嗎????，想掌握程序的靈魂嗎???那么就必須踏上這樣一條漫長的道路????，我們要做的，就是斬妖除魔????，打怪升級！????當(dāng)然切記不可??走火入魔??，每日打怪，日日累積，終能成圣????！今天就開啟我們的斬妖之旅！????

LeetCode-105.從前序與中序遍歷序列構(gòu)成二叉樹：

題目：

給定兩個(gè)整數(shù)數(shù)組 preorder 和 inorder ，其中 preorder 是二叉樹的先序遍歷， inorder 是同一棵樹的中序遍歷，請構(gòu)造二叉樹并返回其根節(jié)點(diǎn)。

示例1：

示例2：

注意事項(xiàng)：

• 1 <= preorder.length <= 3000
• inorder.length == preorder.length
• -3000 <= preorder[i], inorder[i] <= 3000
• preorder 和 inorder 均 無重復(fù) 元素
• inorder 均出現(xiàn)在 preorder
• preorder 保證 為二叉樹的前序遍歷序列
• inorder 保證 為二叉樹的中序遍歷序列

解法：

??思路：

??我們在學(xué)習(xí)二叉樹的時(shí)候，很早就會了使用前序和中序或者中序和后序的序列來還原一顆二叉樹。找到根節(jié)點(diǎn)位置將根節(jié)點(diǎn)創(chuàng)建出來，用左右子樹接收根節(jié)點(diǎn)左右子樹的前中序遍歷的結(jié)果。接著向左子樹和右子樹分別重復(fù)上述操作，就可以遞歸構(gòu)建一顆二叉樹、

??1、我們把前序遍歷數(shù)組的左右子樹給找出來，所以需要中序遍歷的結(jié)果來，用pos作為下標(biāo)，只要中序遍歷數(shù)組的值不等于前序遍歷數(shù)組的第一個(gè)值，pos就++，最后得到的pos就是根節(jié)點(diǎn)。
??2、創(chuàng)建根節(jié)點(diǎn)，將前序遍歷的第一個(gè)數(shù)組放入根節(jié)點(diǎn)。
??3、使用兩個(gè)臨時(shí)數(shù)組分別接收前序和中序遍歷結(jié)果（pos是用來索引區(qū)間的下標(biāo)），然后向左子樹遞歸，遞歸完成之后將兩個(gè)數(shù)組清空，同樣，再用這兩個(gè)數(shù)組接收右子樹前序中序遍歷的結(jié)果，將右子樹遞歸處理，最后返回根節(jié)點(diǎn)即可。

??代碼實(shí)現(xiàn)：

/**
 * 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();//下標(biāo)以及二叉樹節(jié)點(diǎn)個(gè)數(shù)
        while(inorder[pos] != preorder[0]) pos++;//找出中序遍歷根節(jié)點(diǎn)位置
        TreeNode *root = new TreeNode(preorder[0]);//創(chuàng)建根節(jié)點(diǎn)
        vector<int> preArr, inArr;//兩個(gè)臨時(shí)數(shù)組接收前序中序的遍歷結(jié)果

        for(int i = 1; i <= pos; i++) preArr.push_back(preorder[i]);//將前序遍歷結(jié)果給數(shù)組preArr
        for(int i = 0; i < pos; i++) inArr.push_back(inorder[i]);//將中序遍歷結(jié)果給inArr
        root -> left = buildTree(preArr, inArr);//左子樹遞歸
        preArr.clear();//清理兩個(gè)臨時(shí)數(shù)組
        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;
    }
};

??這是一道力扣的中等題，總的來說也并不算很難，理解掌握對前序遍歷與中序遍歷遞歸構(gòu)建的過程才是最重要的。文章來源地址http://www.zghlxwxcb.cn/news/detail-751390.html

到了這里，關(guān)于每日一題：LeetCode-105.從前序遍歷與中序遍歷構(gòu)造二叉樹的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！