要求:通过二叉树的前序和中序遍历序列构建一颗二叉树
代码如下:
1 struct TreeNode {
2 int val;
3 TreeNode *left;
4 TreeNode *right;
5 TreeNode(int x): val(x),left(NULL), right(NULL) {}
6 };
7
8 typedef vector<int>::iterator Iter;
9 TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder)
10 {
11 return buildTreeRecur(preorder.begin(), preorder.end(), inorder.begin(), inorder.end());
12 }
13
14 TreeNode *buildTreeRecur(Iter pstart, Iter pend, Iter istart, Iter iend)
15 {
16 if(pstart == pend || istart == iend)
17 return NULL;
18 int ival = *pstart;
19 Iter ipos = find(istart, iend, ival);
20 TreeNode *res = new TreeNode(ival);
21 res->left = buildTreeRecur(pstart + 1, pstart+1+(ipos-istart), istart, ipos);
22 res->right = buildTreeRecur(pstart+1+(ipos-istart), pend, ipos+1, iend);
23 return res;
24 }