106. Construct Binary Tree from Inorder and Postorder Traversal(根据中序和后序遍历构建二叉树)
/* ***********************************************
1Author :111qqz
2Created Time :2017年04月05日 星期三 16时49分57秒
3File Name :106.cpp
4************************************************ */
5/**
6 * Definition for a binary tree node.
7 * struct TreeNode {
8 * int val;
9 * TreeNode *left;
10 * TreeNode *right;
11 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
12 * };
13 */
14class Solution {
15public:
16 TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
17 int siz = inorder.size();
18 if (siz==0) return NULL;
19 int rt = postorder[siz-1];
20 int pos = -1;
21 for ( int i = 0 ; i < siz; i++)
22 {
23 if (inorder[i]==rt)
24 {
25 pos = i ;
26 break;
27 }
28 }
29 TreeNode *head = new TreeNode(rt);
30 vector<int>in,post;
31 for ( int i = 0 ; i < pos ; i++)
32 {
33 in.push_back(inorder[i]);
34 post.push_back(postorder[i]);
35 }
36 head->left = buildTree(in,post);
37 in.clear();
38 post.clear();
39 for ( int i = pos + 1 ; i < siz ; i++)
40 {
41 in.push_back(inorder[i]);
42 post.push_back(postorder[i-1]);
43 }
44 head->right = buildTree(in,post);
45 return head;
46 }
47};