文章目录
Leetcode105
1.问题描述
2.解决方案
解法一：递归
思路
基本思路：
1.找到根在中序的位置，进而构造左右子树的前中序列，然后递归，然后返回根即可
2.当然需要进行很必要的检查！
if(preorder.size()==0||inorder.size()==0) return nullptr;
if(i==inorder.size()) return nullptr;
代码实现
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if(preorder.size()==0||inorder.size()==0) return nullptr;
TreeNode* root=new TreeNode;
root->val=preorder[0];
int i;
for(i=0;i<inorder.size();i++){
if(root->val==inorder[i]) break;
}
//找到根在中序中的位置是i
if(i==inorder.size()) return nullptr;
//1.构造左子树的新的preorder
vector<int> leftNewPreorder;
for(int k=1;k<=i;k++){
leftNewPreorder.push_back(preorder[k]);
}
//2.构造右子树的新的preorder
//删除preorder[0]到preorder[i]的元素
preorder.erase(preorder.begin(),preorder.begin()+i+1);
//1.构造左子树的新的inorder
vector<int> leftNewInorder;
for(int k=0;k<=i-1;k++){
leftNewInorder.push_back(inorder[k]);
}
//2.构造右子树的新的inorder
//删除inorder[0]到inorder[i]的元素
inorder.erase(inorder.begin(),inorder.begin()+i+1);
//
root->left = buildTree(leftNewPreorder,leftNewInorder);
root->right = buildTree(preorder,inorder);
//
return root;
}
};
解法二：递归优化
—思路
就是在上一种递归中，我们跟根据先序结果得到根节点，然后遍历中序找到根节点在中序序列中的位置index，这样的操作比较耗时，我们可以在构造前，先构造哈希表。
—经验
1.对于同一个序列反复查找的可以想办法用哈希简化
2.尤其是最初给了全部的序列，很方便我们建立哈希表
3.index=i直接计算新的preorder_begin等等这种错误一定要避免可以看下面的分析，举例子一定要举递归几层后的例子更具有代表性！
—代码实现
a.错误写法
错误在于理解性的错误，没有分析一般情况，而只是看了第一层，找到了下标i，就想着直接得到新的preorder_begin等等，由于是第一层嘛，所以其实index为i就能代表长度信息，但是其实当递归到整个序列的中间时，index为i不能代表任何东西，所以要通过长度来计算新的preorder_begin，下次递归一定要举例递归两三层后的情况！
class Solution1 {
public:
unordered_map<int,int> map;
TreeNode* build(vector<int>& preorder, vector<int>& inorder, int preorder_begin, int preorder_end, int inorder_begin, int inorder_end) {
if(preorder_begin>preorder_end||inorder_begin>inorder_end) return nullptr;
TreeNode* root=new TreeNode;
root->val=preorder[preorder_begin];
//找到根在中序中的位置是i
int i=map[root->val];
//
root->left = build(preorder,inorder,preorder_begin+1,preorder_begin+i,inorder_begin,inorder_begin+i-1);
root->right = build(preorder,inorder,preorder_begin+i+1,preorder_end,inorder_begin+i+1,inorder_end);
//
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder){
//这样提前计算只用算一次
int n=preorder.size();
//建立哈希表
for(int i=0;i<n;i++){
map[inorder[i]]=i;
}
//调用
return build(preorder,inorder,0,n-1,0,n-1);
}
};
b.正确写法
通过左右子树前中序列长度来得到新的preorder_begin等，当然还可以吧计算机结果直接放在递归函数参数中，当然可以节省很多时间，但是不是那么清晰，建议先算出来然后注释掉，既清晰又不耗时间！
class Solution {
public:
unordered_map<int,int> map;
TreeNode* build(vector<int>& preorder, vector<int>& inorder, int preorder_begin, int preorder_end, int inorder_begin, int inorder_end) {
if(preorder_begin>preorder_end||inorder_begin>inorder_end) return nullptr;
TreeNode* root=new TreeNode;
root->val=preorder[preorder_begin];
//找到根在中序中的位置是i
int i=map[root->val];
//计算长度
//左子树前中序长度
int leftLong=i-inorder_begin;
//右子树前中序长度
int rightLong=inorder_end-i;
//递归
int left_new_preorder_begin=preorder_begin+1;
int left_new_preorder_end=preorder_begin+1+leftLong-1;
int left_new_inorder_begin=inorder_begin;
int left_new_inorder_end=inorder_begin+leftLong-1;
root->left = build(preorder,inorder,left_new_preorder_begin,left_new_preorder_end,left_new_inorder_begin,left_new_inorder_end);
int right_new_preorder_begin=preorder_begin+1+leftLong;
int right_new_preorder_end=preorder_end;
int right_new_inorder_begin=inorder_begin+leftLong+1;
int right_new_inorder_end=inorder_end;
root->right = build(preorder,inorder,right_new_preorder_begin,right_new_preorder_end,right_new_inorder_begin,right_new_inorder_end);
//返回
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder){
//这样提前计算只用算一次
int n=preorder.size();
//建立哈希表
for(int i=0;i<n;i++){
map[inorder[i]]=i;
}
//调用
return build(preorder,inorder,0,n-1,0,n-1);
}
};
class Solution2 {
public:
unordered_map<int,int> map;
TreeNode* build(vector<int>& preorder, vector<int>& inorder, int preorder_begin, int preorder_end, int inorder_begin, int inorder_end) {
if(preorder_begin>preorder_end||inorder_begin>inorder_end) return nullptr;
TreeNode* root=new TreeNode;
root->val=preorder[preorder_begin];
//找到根在中序中的位置是i
int i=map[root->val];
//计算长度
//左子树前中序长度
int leftLong=i-inorder_begin;
//右子树前中序长度
int rightLong=inorder_end-i;
//递归
root->left = build(preorder,inorder,preorder_begin+1,preorder_begin+1+leftLong-1,inorder_begin,inorder_begin+leftLong-1);
root->right = build(preorder,inorder,preorder_begin+1+leftLong,preorder_end,inorder_begin+leftLong+1,inorder_end);
//返回
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder){
//这样提前计算只用算一次
int n=preorder.size();
//建立哈希表
for(int i=0;i<n;i++){
map[inorder[i]]=i;
}
//调用
return build(preorder,inorder,0,n-1,0,n-1);
}
};
解法三：迭代(我还没看)
class Solution {
private:
unordered_map<int, int> index;
public:
TreeNode* myBuildTree(const vector<int>& preorder, const vector<int>& inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
if (preorder_left > preorder_right) {
return nullptr;
}
// 前序遍历中的第一个节点就是根节点
int preorder_root = preorder_left;
// 在中序遍历中定位根节点
int inorder_root = index[preorder[preorder_root]];
// 先把根节点建立出来
TreeNode* root = new TreeNode(preorder[preorder_root]);
// 得到左子树中的节点数目
int size_left_subtree = inorder_root - inorder_left;
// 递归地构造左子树，并连接到根节点
// 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
root->left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
// 递归地构造右子树，并连接到根节点
// 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
root->right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n = preorder.size();
// 构造哈希映射，帮助我们快速定位根节点
for (int i = 0; i < n; ++i) {
index[inorder[i]] = i;
}
return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
}
};