[二叉树]leetcode105：从前序与中序遍历序列构造二叉树(medium)

二叉树]leetcode105：从前序与中序遍历序列构造二叉树(medium)"/>

[二叉树]leetcode105：从前序与中序遍历序列构造二叉树(medium)

题目：

题解：可参考从中序与后序遍历序列构造二叉树

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {if(preorder.empty()||inorder.empty()) return nullptr;TreeNode *root=new TreeNode(*preorder.begin());//前序数组的第一个元素为根节点auto it=find(inorder.begin(),inorder.end(),*preorder.begin());//在中序数组中寻找指向根节点的迭代器vector<int> iLeft(inorder.begin(),it),iRight(it+1,inorder.end());//左右子树中序数组int size=iLeft.size();vector<int> pLeft(preorder.begin()+1,preorder.begin()+1+size),pRight(preorder.begin()+1+size,preorder.end());//左右子树前序数组root->left=buildTree(pLeft,iLeft);root->right=buildTree(pRight,iRight);return root;}
};