去哪网的笔试题----动态输入二叉树前序遍历和中序遍历的结果,然后输出它的层次遍历结果

时间:2021-05-20 17:31:43

思路:要输出层次遍历的结果,必须先重建二叉树。我在以前的博客中有讲过怎么重建二叉树,层次遍历借助队列来完成。

struct BinaryTreeNode
{
	int value;
	BinaryTreeNode* left;
	BinaryTreeNode* right;
};
//重建二叉树
BinaryTreeNode* Construct(int* preorder,int* preorderend,int* inorder,int* inorderend)
{
	if(preorder==NULL||preorderend==NULL||inorder==NULL||inorderend==NULL)
		return NULL;
	int rootval=preorder[0];  //根节点的值
	BinaryTreeNode* root=new BinaryTreeNode();
	root->value =rootval;
	if(preorder==preorderend)  //只有一个节点
	{
		if(inorder==inorderend)
			return root;
		else  //中序数组中不只有一个节点,异常
			return NULL;
	}
	//在中序数组中,找root节点
	int* rootinorder=inorder;
	while(rootinorder!=inorderend&&rootval!=(*rootinorder))  
		++rootinorder;
	if(rootinorder==inorderend&&rootval!=(*rootinorder)) //没有找到
		return  NULL;
	int len=rootinorder-inorder;  //左子树的长度
	if(len>0)
	{
		//构建左子树
		root->left =Construct(preorder+1,preorder+len,inorder,rootinorder-1);
	}
	if(len<preorderend-preorder)  //左子树长度<总长度
	{
		//构建右子树
		root->right =Construct(preorder+len+1,preorderend,rootinorder+1,inorderend);
	}
	return root;
}
//层次遍历
void Levelorder(BinaryTreeNode* root)
{
	if(root==NULL)
		return;
	queue<BinaryTreeNode*> q;
	q.push(root);
	while(!q.empty())
	{
		BinaryTreeNode* cur=q.front ();
		cout<<cur->value <<" ";
		q.pop();
		if(cur->left !=NULL)
		{
			q.push (cur->left );
		}
		if(cur->right !=NULL)
		{
			q.push (cur->right );
		}
	}


}

void test()
{
	int n=0;
	cin>>n; //树的节点个数
	int* preorder=new int[n];
	int* inorder=new int[n];
	for(int i=0;i<n;++i)
	{
		cin>>preorder[i];
	}
	for(int j=0;j<n;j++)
	{
		cin>>inorder[j];
	}
	BinaryTreeNode* root=Construct(preorder,preorder+n-1,inorder,inorder+n-1);
	Levelorder(root);
}