从二叉树的 中序遍历 和 前（后）序遍历可以唯一地确定一棵二叉树。
前序： 2 7 9 4 6 1
中序: 9 7 2 6 4 1
思路：
1. 根据前序的第一个节点找到 root 节点。 在中序中根据 root 节点将左子树节点 ( 9 7 ) 和 右子树节点 ( 6 4 1 ) 分开；
2. 递归地解决 左子树 和 右子树
/**
* Definition for binary tree
* 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) {
assert(preorder.size() == inorder.size());
return buildTree(preorder.begin(), preorder.end(), inorder.begin(), inorder.end());
}
private:
typedef vector<int>::const_iterator ITERATOR;
TreeNode *buildTree(ITERATOR pre_begin, ITERATOR pre_end, ITERATOR in_begin, ITERATOR in_end){
//EXIT
assert((pre_end - pre_begin) == (in_end - in_begin));
if(pre_begin == pre_end) return NULL;
TreeNode *root = new TreeNode(*pre_begin);
//find root node in inorder traversal to get left tree and right tree
int i(0);
ITERATOR left_end = in_begin;
for(; *left_end != *pre_begin; ++i, ++left_end);
root->left = buildTree(pre_begin+1, pre_begin+i+1, in_begin, in_begin+i);
root->right = buildTree(pre_begin+i+1, pre_end, in_begin+i+1, in_end);
return root;
}
};