声明：本系列博客是对何海涛《剑指offer》的关键点总结。
1.不分行从上到下打印二叉树
1.1. 问题描述
从上到下打印出二叉树的每一个结点，同一层的结点按照从左到右的顺序打印。
如二叉树（8（6（5，7），10（9，11）））打印出8 6 10 5 7 9 11
1.2. 解决思路
1）使用队列保存要访问的结点；
2）从根结点开始，每次打印结点的时候，如果该结点有子结点，则把该结点的子结点放入队列的末尾。
3）从队列的头部取出最早放进去的结点，重复2）直到队列中所有的结点被打印出来。
1.3. 代码实现
/*struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;//构造函数使用列表法初始化数据成员。c++允许在struct内定义成员函数，c语言不允许TreeNode(int x) : val(x), left(NULL), right(NULL) {}};*/class Solution {public:vector<int> PrintFromTopToBottom(TreeNode* root) {vector<int> res;queue<TreeNode*> q;if (root == NULL)return res; q.push(root);while(q.size() != 0){TreeNode* node = q.front();q.pop();res.push_back(node->val);if(node->left != NULL)q.push(node->left);if(node->right != NULL)q.push(node->right);}return res; }};
2.分行从上到下打印二叉树
2.1 问题描述
从上到下打印出二叉树的每一个结点，同一层的结点按照从左到右的顺序打印，每一层打印到一行。
如二叉树（8（6（5，7），10（9，11）））打印出：
8
6 10
5 7 9 11
2.2 解决思路
在问题1的基础上，添加两个变量：
int toBePrinted：表示当前层中还有多少个需要打印；
int nextLevelNum：表示下一层结点的数目；
2.3 代码实现
与问题1的差异用//*****标记
struct BinaryTreeNode {int value;BinaryTreeNode* pLeft;BinaryTreeNode* pRight;};void PrintFromTopToBottom(BinaryTreeNode * pTreeRoot){if (!pTreeRoot)return;int toBePrinted = 1;//*****int nextLevelNum = 0;//*****queue<BinaryTreeNode*> q;q.push(pTreeRoot);while (!q.empty()){BinaryTreeNode * pNode = q.front();q.pop();toBePrinted--;//*****cout << pNode->value << " ";if (pNode->pLeft){q.push(pNode->pLeft);nextLevelNum++;//*****}if (pNode->pRight){q.push(pNode->pRight);nextLevelNum++;//*****}//*****控制转行输出if (toBePrinted == 0){cout << endl;toBePrinted = nextLevelNum;nextLevelNum = 0;}}}
3. 之字形打印二叉树
3.1 问题描述
3.2 解决思路
根绝问题描述可知，奇数层从左到右打印，偶数层从右到左打印，即先访问的结点，其子结点反而是后打印的，所以是一个明显的后进先出结构，需要借助两个栈来完成。
1）如果打印的是奇数层（从左到右），使用1表示奇数，则在第一个栈中，先保存其左子结点，后保存右子结点；
2）如果打印的是偶数层（从右到左），使用0表示偶数，则在第二个栈中，先保存其右子结点，后保存左子结点；
3.3 代码实现
struct BinaryTreeNode {int value;BinaryTreeNode* pLeft;BinaryTreeNode* pRight;};void PrintFromTopToBottom(BinaryTreeNode * pTreeRoot){if (!pTreeRoot)return;stack<BinaryTreeNode*> istack[2];int current = 1;//1表示奇数层，与0不停更替int next = 0;//0表示偶数层，与1不停更替istack[current].push(pTreeRoot);while (!istack[0].empty() && !istack[1].empty()){BinaryTreeNode * pNode = istack[current].top();istack[current].pop();cout << pNode->value << " ";//奇数层先保存左结点，后保存右结点if (current == 1){if (pNode->pLeft)istack[next].push(pNode->pLeft);if (pNode->pRight)istack[next].push(pNode->pRight);}//偶数层先保存右结点，后保存左结点else{if (pNode->pRight)istack[next].push(pNode->pRight);if (pNode->pLeft)istack[next].push(pNode->pLeft);}//判断是否转行进入下一层if (istack[current].empty()){cout << endl;current = 1 - current;next = 1 - next;}}}
