某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点
代码class Solution {
public:
TreeNode* buildTree(vector& preorder, vector& inorder) {
if(preorder.size()==0&&inorder.size()==0) return NULL;
auto headroot=find(inorder.begin(),inorder.end(),preorder[0]);
TreeNode*root=new TreeNode(preorder[0]);
vectorinorderleft(inorder.begin(),headroot);
vectorinorderright(headroot+1,inorder.end());
int n=inorderleft.size();
vectorpreorderleft(preorder.begin()+1,preorder.begin()+1+n);
vectorpreorderright(preorder.begin()+1+n,preorder.end());
root->left=buildTree(preorderleft,inorderleft);
root->right=buildTree(preorderright,inorderright);
return root;
}
};
思路
先找到根节点，即前序遍历数组的第一个数
在中序遍历中找到根节点，根节点之前为左子树，之后为右子树
根据找出的左右子树找出前序遍历中的左右子树
左右子树递归
…
