难度 简单
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
例如:
给定二叉树: [3,9,20,null,null,15,7],
返回其层次遍历结果：
1
2
3
4
5
| [
[3],
[9,20],
[15,7]
]
|
提示：
节点总数 <= 1000
注意：本题与主站 102 题相同：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
解题思路：
建议先做 面试题32 - I. 从上到下打印二叉树 再做此题，两题仅有微小区别，即本题需将 每一层打印到一行 。
I. 按层打印： 题目要求的二叉树的 从上至下 打印（即按层打印），又称为二叉树的 广度优先搜索（BFS）。BFS 通常借助 队列 的先入先出特性来实现。
II. 每层打印到一行： 将本层全部节点打印到一行，并将下一层全部节点加入队列，以此类推，即可分为多行打印。
代码
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
|
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
int i,N;
if(!root) return res;
TreeNode* Node;
queue<TreeNode*> que;
que.push(root);
while(!que.empty())
{
N = que.size();
vector<int> rol;
for(i = 0;i < N;i++)
{
Node = que.front();
rol.push_back(Node->val);
que.pop();
if(Node->left != NULL) que.push(Node->left);
if(Node->right != NULL) que.push(Node->right);
}
res.push_back(rol);
}
return res;
}
};
|
难度 中等
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
例如:
给定二叉树: [3,9,20,null,null,15,7],
返回其层次遍历结果：
1
2
3
4
5
| [
[3],
[20,9],
[15,7]
]
|
提示：
节点总数 <= 1000
思路
解题思路：
面试题32 - I. 从上到下打印二叉树 主要考察 树的按层打印 ；
面试题32 - II. 从上到下打印二叉树 II 额外要求 每一层打印到一行 ；
本题额外要求 打印顺序交替变化（建议按顺序做此三道题）。
BFS层序遍历，每遍历完两层就将要添加的行内数据反转一次
代码
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
|
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
int i,N;
if(!root) return res;
TreeNode* Node;
queue<TreeNode*> que;
que.push(root);
while(!que.empty())
{
N = que.size();
vector<int> rol;
for(i = 0;i < N;i++)
{
Node = que.front();
rol.push_back(Node->val);
que.pop();
if(Node->left != NULL) que.push(Node->left);
if(Node->right != NULL) que.push(Node->right);
}
if( res.size()%2 == 1) reverse(rol.begin(), rol.end());
res.push_back(rol);
}
return res;
}
};
|
