1. 题目
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
2. 示例
示例一：
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
示例 2:
输入: preorder = [-1], inorder = [-1]
输出: [-1]
3. 分析
1.前序和中序可以构造二叉树，中序和后续也可以构造二叉树，但是前序和后序不能构造二叉树。
2.因为有中序就可以确定左子树和右子树区间。而用前序下标可以确定节点在根的左子树还是右子树。所以中序用区间，前序用下标
3.用前序第一个节点做根，再去中序里面找这个根节点，中序里这个节点的左区间就是它的左子树，右区间就是它的右子树，递归左子树与右子树，就可以构建这棵树。递归过程如下：
4. 代码实现
1. /** 2. * Definition for a binary tree node. 3. * struct TreeNode { 4. * int val; 5. * TreeNode *left; 6. * TreeNode *right; 7. * TreeNode() : val(0), left(nullptr), right(nullptr) {} 8. * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} 9. * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} 10. * }; 11. */ 12. class Solution { 13. public: 14. TreeNode* _buildTree(vector<int>& preorder,int& pi,vector<int>& inorder,int inBegin,int inEnd) 15. { 16. if(inBegin > inEnd) 17. { 18. return nullptr; 19. } 20. 21. TreeNode* root = new TreeNode(preorder[pi]); 22. ++pi; 23. int rooti = inBegin; 24. 25. //在中序数组中找前序第pi个节点 26. while(rooti <= inEnd) 27. { 28. if(root->val == inorder[rooti]) 29. { 30. break; 31. } 32. else 33. { 34. ++rooti; 35. } 36. } 37. 38. //找到后就递归中序的左子树区间和右子树驱区间 39. root->left = _buildTree(preorder,pi,inorder,inBegin,rooti-1); 40. root->right = _buildTree(preorder,pi,inorder,rooti+1,inEnd); 41. return root; 42. } 43. TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 44. { 45. int i = 0;//递归的入参，递归过程中需要修改 46. return _buildTree(preorder,i,inorder,0,inorder.size()-1); 47. } 48. }; 49.
