问题描述
分析
逻辑上,从前序遍历中依次从前往后获取根结点,从中序里获取根结点的序号后可以获取左子树和右子树,递归构建树即可。
分治/递归
class Solution {
public:
vector<int> preorder;
vector<int> inorder;
unordered_map<int, int> um;
// 分治
TreeNode* solve(int pre_l, int pre_r, int in_l, int in_r) {
if (in_l > in_r || pre_l > pre_r) {
return nullptr;
}
int root_index = um[preorder[pre_l]];
TreeNode* root = new TreeNode();
root->val = inorder[root_index];
int n = root_index-in_l;
root->left = solve(pre_l+1, pre_l+n+1, in_l, root_index-1);
root->right = solve(pre_l+n+1, pre_r, root_index+1, in_r);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
this->preorder = preorder;
this->inorder = inorder;
for (int i = 0; i < inorder.size(); i++) {
um[inorder[i]] = i; // 值为x的结点在中序遍历中是第i个
}
TreeNode* root;
root = solve(0, preorder.size()-1, 0, inorder.size()-1);
return root;
}
};
拓展
事实上,solve的第二个参数pre_r可以更大,甚至可以去掉,因为每次递归只需找到该子树的前序遍历的第一个元素即可。
class Solution {
public:
vector<int> preorder;
vector<int> inorder;
unordered_map<int, int> um;
// 分治
TreeNode* solve(int pre_l, int in_l, int in_r) {
if (in_l > in_r) {
return nullptr;
}
int root_index = um[preorder[pre_l]];
TreeNode* root = new TreeNode();
root->val = inorder[root_index];
int n = root_index-in_l; // 左子树结点数量
root->left = solve(pre_l+1, in_l, root_index-1);
root->right = solve(pre_l+n+1, root_index+1, in_r);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
this->preorder = preorder;
this->inorder = inorder;
for (int i = 0; i < inorder.size(); i++) {
um[inorder[i]] = i; // 值为x的结点在中序遍历中是第i个
}
TreeNode* root;
root = solve(0, 0, inorder.size()-1);
return root;
}
};
该代码也能ac。
标签:pre,preorder,index,int,root,中序,二叉树,inorder,105 From: https://www.cnblogs.com/saulstavo/p/18597236