本文为剑指 offer 系列第五十六篇。
主要知识点为二叉树，就是层序遍历的变形而已。
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
解题思路
层序遍历的思路。
通过队列来保存每一层的节点，方便下一层的遍历,同时本层的结果要放在本层的数组中，
由于要之字形进行保存，也就是说奇数层和偶数层要分别处理，所以要记录层数,用于之后的判断。
- 单数层添加的时候插入到本层数组的后面，实现从左到右依次添加的效果;
- 双数层添加的时候每次插入到数组的头部，实现类似从右往左添加的效果。
解题代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| /*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
vector<vector<int> > Print(TreeNode* root) {
if(!root) return {};
int levelnum = 1;
vector<vector<int>> res;
queue<TreeNode*> q{{root}};
while(!q.empty()){
vector<int> level;
for(int i = q.size();i>0;i--){
auto a = q.front(); q.pop();
if(levelnum%2 == 1){
level.push_back(a->val);
}else{
level.insert(level.begin(),a->val);
}
if(a->left) q.push(a->left);
if(a->right) q.push(a->right);
}
res.push_back(level);
levelnum++;
}
return res;
}
};
|
时间复杂度为O(n),空间复杂度为O(n)
以上，本题结束！