题目描述
请实现一个函数按照之字形顺序从上向下打印二叉树。
即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
数据范围
树中节点的数量 [0,1000]。
样例
输入如下图所示二叉树[8, 12, 2, null, null, 6, 4, null, null, null, null] 8 / \ 12 2 / \ 6 4 输出：[[8], [2, 12], [6, 4]]
方法一：BFS O(n)
这道题同样和按层打印的操作几乎一样，只是在此基础上又加了一个按 Z 字形打印的条件。我们还是按照正常的遍历每层结点的操作来，只是额外设置一个变量 flag 并初始化为 1 ，每层遍历开始都乘以 -1 。这样在每层遍历结束后可以通过 flag 来判断该层的结点是正向输出还是反向输出。
我们拿题目的样例来举例，看看具体的实现过程：
初始化： 将根结点推入队列中，并将 flag 初始化为 1 。
第一轮遍历：flag * -1 = -1 且 k = 1 ，将队列中元素弹出放入临时数组 temp 中并将其孩子结点推入队列当中。更新 ans 数组，发现 flag = -1 故不用反转数组，直接将 temp 更新到 ans 中即可。
第二轮遍历： flag * -1 = 1 且 k = 2 ，将队列中元素弹出放入临时数组 temp 中并将其孩子结点推入队列当中。更新 ans 数组，发现 flag = 1 故要反转 temp 数组，然后再将 temp 更新到 ans 中。
第三轮遍历： flag * -1 = -1 且 k = 2 ，将队列中元素弹出放入临时数组 temp 中并将其孩子结点推入队列当中。更新 ans 数组，发现 flag = -1 故不用反转数组，直接将 temp 更新到 ans 中即可。
返回答案： 返回 ans 即可。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<vector<int>> printFromTopToBottom(TreeNode* root) { if (!root) return {}; vector<vector<int>> ans; queue<TreeNode*> q; q.push(root); int flag = 1; while (!q.empty()) { int k = q.size(); vector<int> temp; flag *= -1; while (k--) { auto t = q.front(); temp.push_back(t->val); q.pop(); if (t->left) q.push(t->left); if (t->right)q.push(t->right); } if (flag == 1) reverse(temp.begin(), temp.end()); ans.push_back(temp); } return ans; } };
欢迎大家在评论区交流~
