思路:
前序遍历,根节点是第一个值;
中序遍历,根节点左侧是左子树,右侧是右子树
利用下标划分递归区间
前序遍历范围:startPre,endPre
左子树范围:startPre+1,startPre+(i-startVin)
右子树范围:startPre+(i-startVin)+1,endPre
中序遍历范围:startVin,endVin
左子树范围:startVin,i-1
右子树范围:i+1,endVin
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) { if(pre.size()<=0 || vin.size()<=0) return nullptr; TreeNode * root = reConstruct(pre, 0, pre.size()-1, vin, 0, vin.size()-1); return root; } TreeNode* reConstruct(vector<int> pre,int startPre,int endPre,vector<int> vin,int startVin,int endVin){ if(startPre>endPre || startVin>endVin) return nullptr; TreeNode * root = new TreeNode(pre[startPre]); //前序遍历的第一个值为根节点 for(int i = startVin;i<=endVin;i++){ if(vin[i] == root->val){ root->left = reConstruct(pre, startPre+1,startPre+i-startVin ,vin, startVin, i-1); root->right = reConstruct(pre, startPre+i-startVin+1, endPre, vin, i+1, endVin); break; //在中序遍历中找到根节点值,跳出循环 } } return root; } };