剑指 Offer 32 - II. 从上到下打印二叉树 II

难度 简单

从上到下按层打印二叉树,同一层的节点按从左到右的顺序打印,每一层打印到一行。

例如:
给定二叉树: [3,9,20,null,null,15,7],

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

返回其层次遍历结果:

1
2
3
4
5
[
[3],
[9,20],
[15,7]
]

提示:

  1. 节点总数 <= 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
/**
* 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>> 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;
}
};

剑指 Offer 32 - III. 从上到下打印二叉树 III

难度 中等

请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。

例如:
给定二叉树: [3,9,20,null,null,15,7],

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

返回其层次遍历结果:

1
2
3
4
5
[
[3],
[20,9],
[15,7]
]

提示:

  1. 节点总数 <= 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
/**
* 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>> 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;
}
};