Note: This article is available in Chinese only. 本文暂无英文版本。
View original
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};