首页 / 算法 / 《剑指offer》:[61]按之字形顺序打印二叉树

《剑指offer》:[61]按之字形顺序打印二叉树

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了《剑指offer》:[61]按之字形顺序打印二叉树，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1722字，纯文字阅读大概需要3分钟。

内容图文

题目：请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三层再按照从左到右打印，其他行以此类推。

例如：按之字形顺序打印二叉树的结果如下图：

技术分享

打印结果：

1

3,2

4,5,6,7

15,14,13,12,11,10,9,8

方案：利用两个栈。时间复杂度O(N)+辅助空间2*O(N)。

具体方法：我们在打印某一结点时，把下一层的子结点保存到相应的栈里。如果当前打印的是奇数层（例如第一层，第三层...第2*n+1层），则先保存左子结点再保存右子结点到栈里；如果当前打印的是偶数层（2*n），则先保存右子结点再保存左子结点。具体分析步骤如下：

技术分享

具体实现代码：
#include <iostream>
#include <stack>
using namespace  std;
struct BinaryTree
{
	int data;
	BinaryTree *pLeft;
	BinaryTree *pRight;
};
BinaryTree *pRoot=NULL;
void CreateTree(BinaryTree *&root)
{
	int data;
	cin>>data;
	if(0==data)
		root=NULL;
	else
	{
		root =new BinaryTree;
		root->data=data;
		CreateTree(root->pLeft);
		CreateTree(root->pRight);
	}
}
void PrintZhi(BinaryTree *root)
{
	if(NULL==root)
		return;
	stack<BinaryTree*> level[2];
	int current=0;
	int next=1;
	level[current].push(root);
	while(!level[0].empty() || !level[1].empty())
	{
		BinaryTree *node=level[current].top();
		level[current].pop();
		cout<<node->data<<" ";
		if(current==0)
		{
			if(node->pLeft!=NULL)//从左端开始入栈；
				level[next].push(node->pLeft);
			if(node->pRight!=NULL)
				level[next].push(node->pRight);
		}
		else
		{
			if(node->pRight!=NULL)
				level[next].push(node->pRight);
			if(node->pLeft!=NULL)
				level[next].push(node->pLeft);
		}
		if(level[current].empty())
		{
			cout<<endl;
			current=1-current;
			next=1-next;
		}
	}
}
void PreOrder(BinaryTree *root)
{
	if(root)
	{
		cout<<root->data<<" ";
		PreOrder(root->pLeft);
		PreOrder(root->pRight);
	}
}
int main()
{
	CreateTree(pRoot);
	cout<<"前序遍历：";
	PreOrder(pRoot);
	cout<<endl;
	cout<<"之字形打印结果如下："<<endl;
	PrintZhi(pRoot);
	system("pause");
	return 0;
}

运行结果：

技术分享

原文：http://blog.csdn.net/gogokongyin/article/details/51787961

内容总结

以上是互联网集市为您收集整理的《剑指offer》:[61]按之字形顺序打印二叉树全部内容，希望文章能够帮你解决《剑指offer》:[61]按之字形顺序打印二叉树所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1084765.html

来源：【匿名】