https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/
输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
示例：
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
限制：
0 <= 节点个数 <= 5000
使用分治思想，递归得到结果
1，先由前序数组得到根节点，在中序数组中找到根节点对应位置，判断左子树和右子树的长度。
2，将左子树和右子树重新当成新树，迭代步骤1.
递归：
1、传递参数：左子树 的前序中序在原树中的位置 pre_l,pre_r;右子树 的前序中序在原树中的位置 in_l,in_r;
2、终止条件：if(pre_l>pre_r ||in_l>in_r) return NULL;
3、基本操作：
新建根节点 TreeNode *root=new TreeNode(preorder[pre_l])
连接左孩子root->left=buildTreeHelper(preorder,inorder,pre_l+1,pre_l+k-in_l,in_l,k-1);
连接右孩子 root->right=buildTreeHelper(preorder,inorder,pre_l+k-in_l+1,pre_r,k+1,in_r);
4、返回根节点root
class Solution {
public:
unordered_map<int,int> map;
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if(preorder.empty() || inorder.empty()) return NULL;
int len=preorder.size();
for(int i=0;i<=len-1;i++){
map[inorder[i]]=i;
}
return buildTreeHelper(preorder,inorder,0,len-1,0,len-1);
}
TreeNode* buildTreeHelper(vector<int>& preorder, vector<int>& inorder,int pre_l,int pre_r,int in_l, int in_r){
if(pre_l>pre_r ||in_l>in_r) return NULL;
TreeNode* root=new TreeNode(preorder[pre_l]);
//遍历inorder 找根节点
// int k=0;
// for(int i=in_l;i<=in_r;i++){
// if(preorder[pre_l]==inorder[i])
// k=i;
// }
//直接map找根节点位置
int k=map[preorder[pre_l]];
root->left=buildTreeHelper(preorder,inorder,pre_l+1,pre_l+k-in_l,in_l,k-1);
root->right=buildTreeHelper(preorder,inorder,pre_l+k-in_l+1,pre_r,k+1,in_r);
return root;
}
};
其中在中序数组inorder[] 遍历找根节点(时间复杂度O(n)）可以采用哈希map(O(1))实现.
复杂度分析：
时间复杂度：O(N)， 其中 N 为树的节点数量。初始化 HashMap 需遍历 inorder ，占用 O(N) 。递归共建立 N个节点，每层递归中的节点建立、搜索操作占用 O(1) ，因此使用 O(N) 时间。
空间复杂度：O(n)，除去返回的答案需要的 O(N) 空间之外，我们还需要使用 O(N) 的空间存储哈希映射，以及 O(H)（其中 h 是树的高度）的空间表示递归时栈空间。这里 h < n，所以总空间复杂度为 O(N)。
