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};