题目描述
剑指 Offer 32 - I. 从上到下打印二叉树
难度中等72
从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。
例如:
给定二叉树: [3,9,20,null,null,15,7]
,
3
/ \
9 20
/ \
15 7
返回:
[3,9,20,15,7]
二叉树节点如下:
public class BinaryTreeNode {
int value;
BinaryTreeNode left;
BinaryTreeNode right;
}
测试用例
- 功能测试(完全二叉树;所有节点只有左子树的二叉树;所有节点只有右子树的二叉树)
- 特殊功能测试(二叉树根节点为空指针;只有一个节点的二叉树)
题目考点
- 考察应聘者的思维能力,想到用队列处理按层遍历。
- 考察应聘者对二叉树及队列的理解。
解题思路
这道题如果能想到队列,编码还是很简单的。不逼逼了!!!
- 先将头节点放入队列
- 当队列不为空的时候,从队列取出一个节点输出
- 判断取出的节点左右节点是否为空,不为空则将他们加入队列
- 循环至队列为空跳出
参考解题
class Solution {
public int[] levelOrder(TreeNode root) {
if(root==null) return new int[0];
Queue<TreeNode> queue = new LinkedList<>(){
{
add(root); }};
ArrayList<Integer> ans = new ArrayList<>();
while(!queue.isEmpty()){
TreeNode tmp = queue.poll();
ans.add(tmp.val);
if(tmp.left!=null)
queue.add(tmp.left);
if(tmp.right!=null)
queue.add(tmp.right);
}
int[] res = new int[ans.size()];
for(int i = 0; i < ans.size(); i++)
res[i] = ans.get(i);
return res;
}
}
剑指 Offer 32 - II. 从上到下打印二叉树 II
难度简单93
从上到下按层打印二叉树,同一层的节点按从左到右的顺序打印,每一层打印到一行。
例如:
给定二叉树: [3,9,20,null,null,15,7]
,
3
/ \
9 20
/ \
15 7
返回其层次遍历结果:
[
[3],
[9,20],
[15,7]
]
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList();
Queue<TreeNode> queue = new LinkedList();
if(root != null) queue.add(root);
while(!queue.isEmpty()){
List<Integer> list = new ArrayList();
int len = queue.size();
for(int i=0;i<len;i++){
TreeNode tmp = queue.poll();
list.add(tmp.val);
if(tmp.left!=null) queue.add(tmp.left);
if(tmp.right!=null) queue.add(tmp.right);
}
res.add(list);
}
return res;
}
}
剑指 Offer 32 - III. 从上到下打印二叉树 III
难度中等86
请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。
例如:
给定二叉树: [3,9,20,null,null,15,7]
,
3
/ \
9 20
/ \
15 7
返回其层次遍历结果:
[
[3],
[20,9],
[15,7]
]
提示:
节点总数 <= 1000
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> res = new ArrayList<>();
if(root != null) queue.add(root);
while(!queue.isEmpty()) {
LinkedList<Integer> tmp = new LinkedList<>();
for(int i = queue.size(); i > 0; i--) {
TreeNode node = queue.poll();
if(res.size() % 2 == 0) tmp.addLast(node.val); // 偶数层 -> 队列头部
else tmp.addFirst(node.val); // 奇数层 -> 队列尾部
if(node.left != null) queue.add(node.left);
if(node.right != null) queue.add(node.right);
}
res.add(tmp);
}
return res;
}
}