1.題目解析

題目來源：105.從前序與中序遍歷序列構(gòu)造二叉樹——力扣

測(cè)試用例

2.算法原理

首先要了解一個(gè)概念

前序遍歷：按照 根節(jié)點(diǎn)->左子樹->右子樹的順序遍歷二叉樹

中序遍歷：按照 左子樹->根節(jié)點(diǎn)->右子樹的順序遍歷二叉樹

題目中我們可知需要根據(jù)給出的前序遍歷序列與中序遍歷序列構(gòu)建一個(gè)二叉樹，解題思路就是通過前序序列確定根節(jié)點(diǎn)，然后根據(jù)找出的根節(jié)點(diǎn)將中序序列分為:[左子樹，根節(jié)點(diǎn)，右子樹]這樣三個(gè)范圍，然后遞歸構(gòu)造左子樹與右子樹，以此類推直到完成構(gòu)建

3.實(shí)戰(zhà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* build(vector<int>& preorder, vector<int>& inorder,int& previ,int inbegin,int inend){if(inbegin > inend){return nullptr;}//創(chuàng)建根節(jié)點(diǎn)TreeNode* root = new TreeNode(preorder[previ]);//通過前序確定根節(jié)點(diǎn)后將中序數(shù)組分為三部分//左子樹 根節(jié)點(diǎn) 右子樹int rooti = inbegin;while(inbegin <= inbegin){if(inorder[rooti] == preorder[previ]){break;}//尋找中序中的根節(jié)點(diǎn)所在的的位置rooti++;}//此時(shí)前序中的根節(jié)點(diǎn)構(gòu)建完成，向后構(gòu)建其他子樹的根節(jié)點(diǎn)previ++;//左子樹遞歸構(gòu)建[inbegin,rooti-1]區(qū)間//右子樹遞歸構(gòu)建[root+1,inend]區(qū)間root->left = build(preorder,inorder,previ,inbegin,rooti-1);root->right = build(preorder,inorder,previ,rooti+1,inend);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int i = 0;return build(preorder,inorder,i,0,preorder.size()-1);}
};