题目
Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
Show Tags
Show Similar Problems
分析
跟上一道题同样的道理。
AC代码
class Solution {
public:
template <typename Iter>
TreeNode* make(Iter in_begin, Iter in_end , Iter post_begin, Iter post_end ) {
if (post_begin == post_end || in_begin == in_end)
return NULL;
int size = post_end - post_begin;
//后序遍历最后一个节点为树的根节点
TreeNode *root = new TreeNode(*(post_begin + size-1));
//在中序遍历结果中查找根节点
Iter iter = find(in_begin, in_end, *(post_begin + size - 1));
//计算左子树个数
int count = iter - in_begin;
if (iter != in_end)
{
//则在inOrder中（0 ， count-1）为左子树中序遍历结果（count+1，size-1）为右子树的中序遍历序列
//在preOrder中（0，count-1）为左子树前序遍历结果（count,size-2）为右子树前序遍历结果
root->left = make(in_begin, iter , post_begin, post_begin + count);
//构造右子树
root->right = make(iter + 1, in_end ,post_begin + count, post_begin + size - 1);
}
return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (inorder.empty() || postorder.empty())
return NULL;
return make(inorder.begin(), inorder.end() ,postorder.begin(), postorder.end());
}
};