#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:

	vector<int> preorder, inorder;

    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {

		TreeNode * root = NULL;

		if(preorder.size() == 0 || inorder.size() == 0)

			return root;

		this->preorder = preorder;

		this->inorder = inorder;

		for(int i = 0; i < inorder.size(); i ++) {

			if(inorder[i] == preorder[0]) {

				root = new TreeNode(preorder[0]);

				int len1 = i;

				int len2 = inorder.size()-i-1;

				root->left = buildParty(1,0, len1);

				root->right = buildParty(len1+1, i+1, len2);

				return root;

			}

		}

    }

	TreeNode *buildParty(const int &p, const int &i, const int &len) {

		if(len <= 0)

			return NULL;

		for(int cursor = 0; cursor < len; cursor++) {

			int pos = cursor+i;

			if(inorder[pos] == preorder[p]) {

				TreeNode *root = new TreeNode(preorder[p]);

				int len1 = cursor;

				int len2 = len-cursor-1;

				root->left = buildParty(p+1, i, len1);

				root->right = buildParty(p+len1+1, pos+1, len2);

				return root;

			}

		}

	}

};

int main() {

	TreeNode *node;

	int in1[10] = {1, 2, 3, 4, 5, 6};

	int in2[10] = {3, 2, 4, 1, 5, 6};

	Solution solution;

	node = solution.buildTree(vector<int>(in1, in1+6), vector<int>(in2, in2+6));

	return 0;

}

#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:

	vector<int> inorder;

	vector<int> postorder;

    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {

		TreeNode *root = NULL;

		if(!inorder.size())

			return root;

		this->inorder = inorder;

		this->postorder = postorder;

		for(int ci = 0; ci < inorder.size(); ci++) {

			if(inorder[ci] == postorder[postorder.size()-1]) {

				root = new TreeNode(inorder[ci]);

				int len1 = ci;

				int len2 = inorder.size()-ci-1;

				root->left = buildParty(0, postorder.size()-len2-2, len1);

				root->right = buildParty(ci+1, postorder.size()-2, len2);

				return root;

			}

		}

    }

	TreeNode *buildParty(const int &i, const int &j, const int &len) {

		if(!len)

			return NULL;

		for(int ci = 0; ci < len; ci ++) {

			int pos = i+ci;

			if(postorder[j] == inorder[pos]) {

				TreeNode *root = new TreeNode(inorder[pos]);

				int len1 = ci;

				int len2 = len-ci-1;

				root->left = buildParty(i, j-len2-1, len1);

				root->right = buildParty(i+ci+1, j-1, len2);

				return root;

			}

		}

	}

};

int main() {

	TreeNode *node;

	int in1[10] = {3, 2, 4, 1, 5, 6};

	int in2[10] = {3, 4, 2, 6, 5, 1};

	Solution solution;

	node = solution.buildTree(vector<int>(in1, in1+6), vector<int>(in2, in2+6));

	return 0;

}