记得第一次遇见类似的题目是在今年的暑假，是pat甲级里的一道题。当时在听了学长的讲解后，并没有充分理解这道题的解题思路。最近打天梯赛和leetcode又遇到了相同的题目，于是决定花功夫掌握这类题目的做法。
题目如下： 根据一棵树的前序遍历与中序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]
leetcode题目连接
解题思路： 首先要回答两个问题： （1）如何使用前序遍历和中序遍历 （2）如何利用已知信息递归的构造二叉树
图片来自leetcode 上面的图片可以非常清晰的得出那两个问题的答案： （1）通过先序遍历可以直接确定根节点的数值，而在知道根节点的数值之后，可以在中后序遍历中得出左子树和右子树的长度，由长度关系进而推到出新的左右子树的前序遍历和中序遍历（过程见图片）。 （2）首先将当前根节点的数值设置为正在构造的二叉树的当前结点的数值，由于（1）已经将左右子树的划分出来，并且对左右子树的处理方式和当前一样，所以此时只需要对左右子树进行递归处理，便可以完成二叉树的创建。 代码如下
class Solution { private: unordered_map<int, int> book; public: TreeNode* creat(vector<int>& pre, vector<int>& ino, int preleft, int preright, int inleft, int inright) { if(preleft > preright) return NULL; //递归出口 int preroot = preleft; int inroot = book[pre[preroot]]; //通过哈希映射快速获得中序遍历根结点的位置 TreeNode* root = new TreeNode(pre[preroot]); root->left = creat(pre, ino, preleft + 1, preleft - inleft + inroot, inleft, inroot - 1); //对左子树递归 root->right = creat(pre, ino, preleft - inleft + inroot + 1, preright, inroot + 1, inright); //对右子树递归 return root; } TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { int n = preorder.size(); for(int i = 0; i < n; i++) book[inorder[i]] = i; //记录中序遍历结点的位置 return creat(preorder, inorder, 0, n - 1, 0, n - 1); } };