思路
首先回忆下，用前序遍历和中序遍历一颗二叉树：
1
/
2 3
/ /
4 5 6 7
前序遍历的结果是:[1,2,4,5,3,6,7]
中序遍历的结果是:[4,2,5,1,6,3,7]
前序遍历的特点是，根节点始终出现在数组的第一位，而中序遍历中根节点出现在数组的中间位置。
根据上面给出的两个数组，首先我们就可以拼出根节点，它就是1。
题目上已说明数组中不存在重复元素，那么由1就可以定位到中序数组的中间位置，中序数组中1左边的部分就是左子树，1右边部分就是右子树。
前序数组怎么切分呢？注意看下面这张图，根节点是橘色，绿色部分是左子树，蓝色部分是右子树。
前序数组的左子树部分+根节点是1,2,4,5，中序数组的左子树部分+根节点是4,2,5,1。这两者的数组长度是一样的。
我们可以根据中序数组的中间位置1，来确定前序数组的左右部分，由于前序数组第一个是根节点，
所以其左边部分是：[1:mid_index]，右半部分是[mid_index+1:]
这里的mid_index是中序数组的中间下标位置。
递归函数实现如下：
- 终止条件:前序和中序数组为空
- 根据前序数组第一个元素，拼出根节点，再将前序数组和中序数组分成两半，递归的处理前序数组左边和中序数组左边，递归的处理前序数组右边和中序数组右边。
动画演示如下：
代码实现
1 /** 2 * Definition for a binary tree node. 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */ 10 class Solution { 11 public: 12 TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { 13 if(preorder.empty()) 14 return NULL; 15 16 return build(preorder, inorder, 0, preorder.size()-1, 0, inorder.size()-1); 17 } 18 19 TreeNode* build(vector<int>& preorder, vector<int>& inorder, 20 int preL, int preR, int inL, int inR) { 21 if(preL > preR || inL > inR) { 22 return NULL; 23 } 24 25 int i; 26 for(i = inL; i < inorder.size(); ++i) 27 if(inorder[i] == preorder[preL]) 28 break; 29 30 TreeNode* root = new TreeNode(preorder[preL]); 31 root->left = build(preorder, inorder, preL+1, preL+(i-inL), inL, i-1); 32 root->right = build(preorder, inorder, preL+(i-inL)+1, preR, i+1, inR); 33 return root; 34 35 } 36 };
复杂度分析
