1.題目解析

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

測試用例

2.算法原理

首先要了解一個概念

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

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

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

3.實戰(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é)點TreeNode* root = new TreeNode(preorder[previ]);//通過前序確定根節(jié)點后將中序數(shù)組分為三部分//左子樹 根節(jié)點 右子樹int rooti = inbegin;while(inbegin <= inbegin){if(inorder[rooti] == preorder[previ]){break;}//尋找中序中的根節(jié)點所在的的位置rooti++;}//此時前序中的根節(jié)點構(gòu)建完成，向后構(gòu)建其他子樹的根節(jié)點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);}
};