C++复习之路:算法与数据结构相关3:二叉树的序列化和反序列化(重建二叉树)
逻辑上还是很简单的,想起来前几天字节的提前批就有面到这道题,结果自己说出了逻辑没写出代码,继续努力吧。
注意:只有前序+中序或中序+后序才能确定一颗二叉树。
主要思路是根据根左右和左根右的特点,递归地找出根节点、子树的根节点,最终完成重建。
//DLR:根左右、LDR:左根右、LRD:左右根 需要注意的是以下代码是建立在前序和中序序列正确的情况下的,并没有针对不匹配的情况写异常处理
TreeNode* rebuildTreePre(vector<int> DLR, vector<int> LDR)//前序+中序的重建
{ //L1、R1,L2、R2分别表示前序遍历和中序遍历序列的下标范围
// 递归出口(遇到叶子节点返回空指针)
if (DLR.empty() || LDR.empty())
return nullptr;
// 建立根节点
TreeNode *head = new TreeNode(DLR[0]);
// 查找中序遍历中根节点的索引值
int root = 0;
for (int i = 0; i < LDR.size(); ++i)
{
if (LDR[i] == DLR[0])
{
root = i;
break;
}
}
// 先序遍历和中序遍历的左右子树vector
vector<int> pre_left, pre_right, vin_left, vin_right;
for (int i = 0; i < root; ++i)
{
pre_left.push_back(DLR[i + 1]);
vin_left.push_back(LDR[i]);
}
for (int i = root + 1; i < DLR.size(); ++i)
{
pre_right.push_back(DLR[i]);
vin_right.push_back(LDR[i]);
}
// 根节点的左右节点
head->left = rebuildTreePre(pre_left, vin_left);
head->right = rebuildTreePre(pre_right, vin_right);
return head;
}
!!!以上代码不够优化,因为其中涉及了多次vector的重建,考虑进一步优化应该在递归的参数中加入左右子树的范围
优化如下:
TreeNode* rebuildTreePre(vector<int> DLR, vector<int> LDR, int L1,int R1,int L2,int R2)//前序+中序的重建
{
// 递归出口(遇到叶子节点返回空指针)
if (L1>R1)
return nullptr;
// 建立根节点
TreeNode *head = new TreeNode(DLR[L1]);
// 查找中序遍历中根节点的索引值
int i = 0;
for ( i = L2; i <=R2; ++i)
{
if (LDR[i] == DLR[L1])
{
break;
}
}
// 先序遍历和中序遍历的左右子树vector
// 根节点i的左右节点
head->left = rebuildTreePre(DLR, LDR,L1+1,L1+i-L2,L2,i-1);
head->right = rebuildTreePre(DLR, LDR, L1 + i - L2+1, R1,i+1, R2);
return head;
}
如果还考虑到参数中值传递会带来不必要的拷贝消耗,可以把消耗大的参数改为引用传递。
修改如下:
TreeNode* rebuildTreePre(const vector<int> & DLR, const vector<int> & LDR, int L1,int R1,int L2,int R2)
甚至考虑到递归实际使用了系统栈,还可以考虑使用非递归的方法来重建二叉树,这里就不展开了。