问题描述：
根据先序数列和中序数列，构造二叉树。如：
先序：[3, 9, 20, 15, 7]
后序：[9, 3, 15, 20, 7]
需构成二叉树为：
3 / \ 9 20 / \ 15 7
解决思路：
对于上图的树来说， 先序遍历为: 3 9 20 15 7 中序遍历为: 9 3 15 20 7 为了清晰表示，我给节点上了颜色，红色是根节点，蓝色为左子树，绿色为右子树。 可以发现的规律是：1. 先序遍历的从左数第一个为整棵树的根节点。 2. 中序遍历中根节点是左子树右子树的分割点。
再看这个树的左子树： 先序遍历为: 9 中序遍历为: 9 依然可以套用上面发现的规律。
右子树： 先序遍历为: 20 15 7 中序遍历为: 15 20 7 也是可以套用上面的规律的。
代码实现：
/**
* 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:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return build(preorder, inorder, 0, preorder.size()-1, 0, inorder.size()-1);
}
TreeNode* build(vector<int>& preorder, vector<int>& inorder, int preStart, int preEnd, int inStart, int inEnd) {
if (inEnd < inStart) return NULL;
int rootVal = preorder[preStart]; // 先序寻找根节点
TreeNode *Node = new TreeNode(rootVal); // 建立二叉树节点
int rootIndex = 0;
for (int i = 0; i < inorder.size(); i++) { // 中序中寻找根节点的索引
if (rootVal == inorder[i]) {
rootIndex = i;
break;
}
}
int lenL = rootIndex - inStart;
int lenR = inEnd - rootIndex;
if (lenL > 0) {
Node->left = build(preorder, inorder, preStart+1, preStart+lenL, inStart, rootIndex-1);
}
if (lenR > 0) {
Node->right = build(preorder, inorder, preStart+lenL+1, preEnd, rootIndex+1, inEnd);
}
return Node;
}
};
学习内容：
1. 之前学过二叉树结构的数据处理，但没有构建过二叉树，此问题学会
TreeNode *Node = new TreeNode(rootVal);
来构建二叉树
2. 学习如何通过先序和中序排列逻辑，来构成二叉树
