1 题目
https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/
2 题意
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/
9 20
/
15 7
限制：
0 <= 节点个数 <= 5000
3 解题思路
author's blog == http://www.cnblogs.com/toulanboy/
3.1 思考切入点
主要利用遍历的特征解题，思考顺序如下：
1、通过先序遍历，可知这棵树的根节点（第1个就是根节点）。
2、通过中序遍历和根节点，由于根节点位于左右子树的中间，故可知左子树的中序遍历、右子树的中序遍历。
3、通过第2步得出的左右子树中序遍历，可知左右子树的节点数。进一步地，结合整棵树先序遍历，可知左子树的先序遍历、右子树的先序遍历。
通过上述3步，就可以分别知道左右子树的先序、中序遍历。循环这个逻辑，进一步细分，就可以还原整颗树。
代码层面，利用递归就可以实现。
3. 2 代码思路：
1、递归步骤
（1）通过先序得到这棵树的根节点。
（2）左子树的根，调用相同逻辑得到。
（3）右子树的根，调用相同逻辑得到。
2、递归边界
当先序遍历的序列为空，说明当前是个空树。
4 代码实现
//author's blog == http://www.cnblogs.com/toulanboy/
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
//该树的先序遍历序列是preorder的[pre_left, pre_right]
//该树的中序遍历序列是inorder的[in_left, in_right]
TreeNode* build(vector<int>& preorder, int pre_left, int pre_right, vector<int>& inorder, int in_left, int in_right) {
if(pre_left > pre_right){
return NULL;
}
//先序遍历的第一个节点就是这棵树的根节点的数值
TreeNode * root = new TreeNode(preorder[pre_left]);
//通过根节点，结合中序遍历，找到左子树的节点数。
int key = preorder[pre_left];
int left_tree_count = 0;
for(int i=in_left; i<=in_right; ++i){
if(inorder[i] != key){
left_tree_count++;
}
else{
break;
}
}
//知道左子树有多少个节点后，就可以进行具体的划分出左子树的先序遍历和中序遍历序列
root->left = build(preorder, pre_left+1, pre_left+left_tree_count, inorder, in_left, in_left+left_tree_count-1);
//原理同上
root->right = build(preorder, pre_left+1+left_tree_count, pre_right, inorder, in_left+left_tree_count+1, in_right);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return build(preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1);
}
};