题目
输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
示例 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7]
示例 2:
Input: preorder = [-1], inorder = [-1] Output: [-1]
解题
和leetcode-105：从前序与中序遍历序列构造二叉树这道题是一样的。
方法一：
class Solution { public: unordered_map<int,int> umap; vector<int> preorder; vector<int> inorder; TreeNode* helper(int left,int right){ if(left>right) return nullptr; int num=preorder.front(); preorder.erase(preorder.begin()); int mid=umap[num]; TreeNode* root=new TreeNode(num); root->left=helper(left,mid-1); root->right=helper(mid+1,right); return root; } TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { this->preorder=preorder; this->inorder=inorder; for(int i=0;i<inorder.size();i++){ umap[inorder[i]]=i; } return helper(0,inorder.size()-1); } };
