我在本地测试没出过问题,但是放到oj系统上就runtime error,错误代码11。
应该是访问到未定义的内存,可是我查了好久都没找到哪里越界了,求指教
#include <cstdio>
#pragma warning(disable:4996)
class TreeNode
{
public:
int data;
TreeNode* fo;
TreeNode* ba;
};
class Tree
{
public:
int size;
TreeNode* first;
TreeNode* last;
Tree();
void AddNew(int data);
void MiddleNode(TreeNode* Node, TreeNode* FindMid);
};
Tree::Tree()
{
size = 0;
TreeNode* temp = new TreeNode();
first = last = temp;
}
void Tree::AddNew(int data)
{
TreeNode* temp = new TreeNode();
temp->data = data;
last->ba = temp;
temp->fo = last;
last = temp;
size++;
}
void Tree::MiddleNode(TreeNode* Node, TreeNode* FindMid)
{
if (first->ba->fo->data!=0)
{
first->ba->fo->ba = first->ba->ba;
first->ba->ba->fo = first->ba->fo;
first->ba = first->ba->ba;
}
else
{
first->ba = first->ba->ba;
}
FindMid->fo->ba = Node;
Node->ba = FindMid;
Node->fo = FindMid->fo;
FindMid->fo = Node;
}
void FindChild(Tree* Pre,Tree* Pos,TreeNode* Node)
{
if (Pre->first->ba==Pre->last&&Pos->first->ba==Pos->last)
{
return;
}
else
{
TreeNode* pretemp = Pre->first->ba->ba;
TreeNode* postemp = Pos->last->fo;
TreeNode* preend = Pre->first->ba;
TreeNode* posend=Pos->last;
int pri,poi;
for (int i = 0; i < Pre->size; i++)
{
if (postemp->data == Pre->first->ba->ba->data)
{
posend = postemp;
poi = i;
}
else
postemp = postemp->fo;
if (pretemp->data == Pos->last->fo->data)
{
preend = pretemp;
pri = i;
}
else
pretemp = pretemp->ba;
}
Tree* LTPr = new Tree();
Tree* LTPo = new Tree();
Tree* RTPr = new Tree();
Tree* RTPo = new Tree();
LTPr->first->ba = Pre->first->ba->ba;
LTPr->last = pretemp->fo;
LTPo->first->ba = Pos->first->ba;
LTPo->last = posend;
LTPo->size = LTPr->size = poi-1;
FindChild(LTPr, LTPo, Pre->first);
RTPr->first->ba = pretemp;
RTPr->last = Pre->last;
RTPo->first->ba = posend->ba;
RTPo->last = Pos->last->fo;
RTPo->size = RTPr->size = Pre->size - poi;
FindChild(RTPr, RTPo, preend);
Pre->MiddleNode(Pre->first->ba,preend);
}
}
Tree* Pre = new Tree();
Tree* Pos = new Tree();
int main()
{
int n = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
int tempdata = 0;
scanf("%d",&tempdata);
Pre->AddNew(tempdata);
}
for (int i = 0; i < n; i++)
{
int tempdata = 0;
scanf("%d", &tempdata);
Pos->AddNew(tempdata);
}
FindChild(Pre,Pos,Pre->first->ba);
TreeNode* prte = Pre->first->ba;
for (int i = 0; i < Pre->size; i++)
{
printf("%d ", prte->data);
prte = prte->ba;
}
return 0;
}
补充OJ问题:
描述
一般来说,给定二叉树的先序遍历序列和后序遍历序列,并不能确定唯一确定该二叉树。
(图一)
比如图一中的两棵二叉树,虽然它们是不同二叉树,但是它们的先序、后序遍历序列都是相同的。
但是对于“真二叉树”(每个内部节点都有两个孩子的二叉树),给定它的先序、后序遍历序列足以完全确定它的结构。
将二叉树的n个节点用[1, n]内的整数进行编号,输入一棵真二叉树的先序、后序遍历序列,请输出它的中序遍历序列。
输入
第一行为一个整数n,即二叉树中节点的个数。
第二、三行为已知的先序、后序遍历序列。
输出
仅一行,给定真二叉树的中序遍历序列。
样例
见英文题面
限制
对于95%的测例:1 ≤ n ≤ 1,000,000
对于100%的测例:1 ≤ n ≤ 4,000,000
输入的序列是{1,2...n}的排列,且对应于一棵合法的真二叉树
时间:2 sec
空间:256 MB
Example
Input
5
1 2 4 5 3
4 5 2 3 1
Output
4 2 5 1 3