1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<stdio.h>
#include<iostream>
#include<vector>
using namespace std;
struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int x):val(x),left(NULL),right(NULL){}
};
class Solution {
public:
	TreeNode* preinCon(const vector<int>& pre, const vector<int>& in) {
		int preLen = pre.size();
		int inLen = in.size();
		if (preLen == 0 || inLen == 0 || preLen != inLen) {
			return NULL;
		}
		TreeNode* root =new TreeNode(pre[0]);
		int root_in = 0;
		for (int i = 0; i < inLen; i++) {
			if (pre[0] == in[i]) {
				root_in = i;
				break;
			}
		}
		vector<int> pre_left;
		vector<int> pre_right;
		vector<int> in_left;
		vector<int> in_right;
		for (int i = 0; i < root_in; i++) {
			in_left.push_back(in[i]);
			pre_left.push_back(pre[i + 1]);
		}
		for (int i = root_in + 1; i < preLen; i++) {
			in_right.push_back(in[i]);
			pre_right.push_back(pre[i]);
		}
		root->left = preinCon(pre_left, in_left);
		root->right = preinCon(pre_right, in_right);
		return root;
	}
	TreeNode* postinCon(const vector<int>& post, const vector<int>& in) {
		int postLen = post.size();
		int inLen = in.size();
		if (postLen == 0 || inLen == 0 || postLen != inLen) {
			return NULL;
		}
		TreeNode* root = new TreeNode(post[postLen - 1]);
		int root_in = 0;
		for (int i = 0; i < inLen; i++) {
			if (post[postLen - 1] == in[i]) {
				root_in = i;
				break;
			}
		}
		vector<int> post_left;
		vector<int> post_right;
		vector<int> in_left;
		vector<int> in_right;
		for (int i = 0; i < root_in; i++) {
			post_left.push_back(post[i]);
			in_left.push_back(in[i]);
		}
		for (int i = root_in; i < postLen - 1; i++) {
			post_right.push_back(post[i]);
			in_right.push_back(in[i + 1]);
		}
		root->left = postinCon(post_left, in_left);
		root->right = postinCon(post_right, in_right);
		return root;
	}
	void InOrder(TreeNode *root)
	{
		if (root == NULL)
			return;
		InOrder(root->left);
		std::cout << root->val << " ";
		InOrder(root->right);
	}
};
int main() {
	int a[5] = { 3,9,20,15,7 };
	int b[5] = { 9,3,15,20,7 };
	int c[5] = { 9,15,7,20,3 };
	vector<int> pre(a, a + 5);
	vector<int> in(b, b + 5);
	vector<int> post(c, c + 5);
	Solution s;
	TreeNode* p=s.preinCon(pre, in);
	s.InOrder(p);
	cout << endl;
	TreeNode* p2 = s.postinCon(post, in);
	s.InOrder(p2);
	return 0;
}