题目描述
请实现一个函数按照之字形顺序从上向下打印二叉树。
即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。
样例
输入如下图所示二叉树[8, 12, 2, null, null, 6, 4, null, null, null, null]
8
/ \
12 2
/ \
6 4
输出:[[8], [2, 12], [6, 4]]
算法
(BFS,层序遍历)
- 跟上面的题是一样的,不过要在遍历到下一层的时候反转一下。那么如何反转呢?加一个zigzag的bool型变量。用来反转cur数组,也就是一行中的数组内的元素。
- 那么加在哪里呢?就在要将cur放进res的那里之前,翻转后,因为要到下一行了,再对zigzag取个反,从而可以达到下一行就不会反转,下下行才会继续反转的效果。
时间复杂度
$O(n)$
因为只会遍历二叉树中的每一个节点,所以时度是$O(n)$
C++ 代码
/**
* 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>> res;
vector<int> cur;
vector<vector<int>> bfs(TreeNode* root)
{
queue<TreeNode*> q;
q.push(root);
q.push(nullptr);
bool zigzag = false;
while(q.size())
{
auto t = q.front();
q.pop();
if(t)
{
cur.push_back(t->val);
if(t->left) q.push(t->left);
if(t->right) q.push(t->right);
}
else
{
if(q.size()) q.push(nullptr);
if(zigzag) reverse(cur.begin(), cur.end());
res.push_back(cur);
cur.clear();
zigzag = !zigzag;
}
}
return res;
}
vector<vector<int>> printFromTopToBottom(TreeNode* root) {
if(!root) return res;
return bfs(root);
}
};