106. Construct Binary Tree from Inorder and Postorder Traversal(根据中序和后序遍历构建二叉树)

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