依据中序和后序遍历序列求二叉树高度的题目,运行正确,但是在OJ里面提交内存超限
根据中序和后序遍历序列求二叉树高度的题目,运行正确,但是在OJ里面提交内存超限
输入的只有不重复的26个字母的序列 输入N种情况的中序和后序遍历序列 然后输出二叉树的高度
建立二叉树和求树的高度用的都是递归算法 OJ里面的内存限制是10000K 这样来说每个序列最多也就递归26次啊 为什么会内存超限呢
------解决思路----------------------
主函数中char inorder[26];char postorder[26];赋初值肯定有问题。你改了再试试看
------解决思路----------------------
把数组的长度改成27试试。
输入的只有不重复的26个字母的序列 输入N种情况的中序和后序遍历序列 然后输出二叉树的高度
建立二叉树和求树的高度用的都是递归算法 OJ里面的内存限制是10000K 这样来说每个序列最多也就递归26次啊 为什么会内存超限呢
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
struct BinaryTreeNode
{
char m_nValue;
BinaryTreeNode* pLeft;
BinaryTreeNode* pRight;
};
// 输入:中序和后序的第一个指针和最后一个指针,
// 递归调用,每次确定当前结点
BinaryTreeNode* ConstructCore_in_post(char* startInorder, char* endInorder, char* startPostorder, char* endPostorder)
{
//后序最后一个结点为根结点
char rootValue = *endPostorder;
BinaryTreeNode* root=new BinaryTreeNode;
root->m_nValue = rootValue;
root->pLeft = root->pRight = NULL;
//递归退出条件
if ( startPostorder==endPostorder && startInorder==endPostorder )
return root;
//在中序中找到当前根节点
char* rootInorder = startInorder;
while(rootInorder<=endInorder && *rootInorder != rootValue )
++rootInorder;
int leftLength = rootInorder - startInorder;
char* leftInorderEnd = startInorder+leftLength-1;
if ( leftLength > 0 )
{
//构建左子树
root->pLeft=ConstructCore_in_post(startInorder,leftInorderEnd,startPostorder, startPostorder+leftLength-1);
}
if ( leftLength < endInorder-startInorder )
{
//构建右子树
root->pRight= ConstructCore_in_post(rootInorder+1,endInorder,startPostorder+leftLength,endPostorder-1);
}
return root;
}
//根据先序和中序构建二叉树
BinaryTreeNode* Construct(char* inorder, char* postorder, int length)
{
if(inorder==NULL || postorder==NULL || length <=0)
return NULL;
return ConstructCore_in_post(inorder, inorder+length-1, postorder, postorder+length-1);
}
void High(BinaryTreeNode *T, int &h)
{
if (T == NULL)
h = 0;
else {
int left_h;
High(T->pLeft, left_h);
int right_h;
High(T->pRight, right_h);
h = 1 + max(left_h, right_h);
}
}
int main()
{
int n;
char inorder[26];
char postorder[26];
cin>>n;
int height;
while(n--){
cin>>inorder;
cin>>postorder;
int len=strlen(inorder);
BinaryTreeNode* pRoot = Construct(inorder,postorder,len);
High(pRoot,height);
cout<<height<<endl;
}
return 0;
}
------解决思路----------------------
主函数中char inorder[26];char postorder[26];赋初值肯定有问题。你改了再试试看
------解决思路----------------------
把数组的长度改成27试试。