给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗二叉树 。
class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (postorder.size() == 0) return NULL;
TreeNode* root = new TreeNode(postorder.back());
if (postorder.size() == 1) return root;
auto it = find(inorder.begin(),inorder.end(),root->val);
vector<int> left_inorder(inorder.begin(),it);
vector<int> right_inorder(it+1,inorder.end());
int dis = distance(inorder.begin(),it);
it = postorder.begin() + dis;
vector<int> left_postorder(postorder.begin(),it);
vector<int> right_postorder(it,postorder.end()-1);
if(left_inorder.size())
{
root->left = buildTree(left_inorder,left_postorder);
}
if(right_inorder.size())
{
root->right = buildTree(right_inorder,right_postorder);
}
return root;
}
};
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if (preorder.size() == 0) return NULL;
TreeNode* root = new TreeNode(preorder.front());
if (preorder.size() == 1) return root;
auto it = find(inorder.begin(),inorder.end(),root->val);
vector<int> left_inorder(inorder.begin(),it);
vector<int> right_inorder(it+1,inorder.end());
int dis = distance(inorder.begin(),it);
it = preorder.begin() + 1 + dis;
vector<int> left_preorder(preorder.begin()+1,it);
vector<int> right_preorder(it,preorder.end());
if(left_inorder.size())
{
root->left = buildTree(left_preorder,left_inorder);
}
if(right_inorder.size())
{
root->right = buildTree(right_preorder,right_inorder);
}
return root;
}
};