LeetCode #106

# Description:

Given inorder and postorder traversal of a tree, construct the binary tree.

## Example:

``````Note
``````

# Code:

``````class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
return buildTree(postorder.begin(), postorder.end(), inorder.begin(), inorder.end());
}

template<typename T>
TreeNode* buildTree(T post_begin, T post_end, T in_begin, T in_end){
if(post_begin==post_end) return NULL; // 到底了，return NULL
if(in_begin==in_end) return NULL;

TreeNode* root = new TreeNode(*prev(post_end)); // for postorder, the root is in the end
auto it_root_inorder = find(in_begin, in_end, *prev(post_end));
int left_size = it_root_inorder-in_begin; // Left subtree size
int right_size = in_end-it_root_inorder-1; // right subtree size

root->left = buildTree(post_begin, next(post_begin, left_size), in_begin, it_root_inorder);
root->right = buildTree(next(post_begin, left_size), prev(post_end), next(it_root_inorder), in_end);

return root;
}
};
``````