Construct Binary Tree from Inorder and Postorder Traversal
Given inorder and postorder traversal of a tree, construct the binary tree.
Note：
You may assume that duplicates do not exist in the tree.
For example, given
inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]
Return the following binary tree:
分析：
每次取postorder的最后一个值mid，将其作为树的根节点
然后从inroder中找到mid，将其分割成为两部分，左边作为mid的左子树，右边作为mid的右子树
tree: 8 4 10 3 6 9 11
Inorder [3 4 6] 8 [9 10 11]
postorder [3 6 4] [9 11 10] 8
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
return buildTree(begin(inorder), end(inorder), begin(postorder), end(postorder));
}
template<class T>
TreeNode* buildTree(T in_first, T in_last, T post_first, T post_last) {
if (in_first == in_last) return nullptr;
if (post_first == post_last) return nullptr;
const auto val = *prev(post_last);
TreeNode* root = new TreeNode(val);
auto in_root_pos = find(in_first, in_last, val);
auto left_size = distance(in_first, in_root_pos);
auto post_left_last = next(post_first, left_size);
root->left = buildTree(in_first, in_root_pos, post_first, post_left_last);
root->right = buildTree(next(in_root_pos), in_last, post_left_last, prev(post_last));
return root;
}
};
递归，时间复杂度o(n),空间复杂度o(\logn)