剑指 Offer 32 - I. 从上到下打印二叉树
题目
剑指 Offer 32 - I. 从上到下打印二叉树 难度：medium
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7返回：
[3,9,20,15,7]提示：
节点总数 <= 1000
方法一：BFS
思路
根据题意，这是二叉树的广度优先搜索（BFS）。BFS 通常借助 队列 的先入先出特性来实现。
- 特例处理： 当树的根节点为空，则直接返回空列表
[]； - 初始化： 打印结果列表
res = []，包含根节点的队列queue = [root]； BFS 循环： 当队列
queue为空时跳出；- 出队： 队首元素出队，记为
node； - 打印： 将
node.val添加至列表tmp尾部； - 添加子节点： 若
node的左（右）子节点不为空，则将左（右）子节点加入队列queue；
- 出队： 队首元素出队，记为
- 返回值： 返回打印结果列表
res即可。
解题
Python：
class Solution:
def levelOrder(self, root: TreeNode) -> List[int]:
if not root: return []
res, queue = [], collections.deque()
queue.append(root)
while queue:
node = queue.popleft()
res.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
return resJava：
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 node = queue.poll();
ans.add(node.val);
if(node.left != null) queue.add(node.left);
if(node.right != null) queue.add(node.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
题目
剑指 Offer 32 - II. 从上到下打印二叉树 II 难度：easy
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]提示：
节点总数 <= 1000
方法一：BFS
思路
跟上一题相差不大，刚好可以验证一下是否掌握了，不多赘述；
解题
Python：
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root: return []
res, queue = [], collections.deque()
queue.append(root)
while queue:
tmp = []
for _ in range(len(queue)):
node = queue.popleft()
tmp.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
res.append(tmp)
return resJava：
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()) {
List<Integer> tmp = new ArrayList<>();
for(int i = queue.size(); i > 0; i--) {
TreeNode node = queue.poll();
tmp.add(node.val);
if(node.left != null) queue.add(node.left);
if(node.right != null) queue.add(node.right);
}
res.add(tmp);
}
return res;
}
}
剑指 Offer 32 - III. 从上到下打印二叉树 III
题目
剑指 Offer 32 - III. 从上到下打印二叉树 III 难度：medium
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7返回其层次遍历结果：
[
[3],
[20,9],
[15,7]
]提示：
节点总数 <= 1000
方法一：BFS
思路
跟之前的题目还是大相庭径的，这题的话，打印顺序交替变化，因此可以考虑双端队列；
解题
Python：
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root: return []
res, deque = [], collections.deque([root])
while deque:
tmp = collections.deque()
for _ in range(len(deque)):
node = deque.popleft()
if len(res) % 2: tmp.appendleft(node.val) # 偶数层 -> 队列头部
else: tmp.append(node.val) # 奇数层 -> 队列尾部
if node.left: deque.append(node.left)
if node.right: deque.append(node.right)
res.append(list(tmp))
return resJava：
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;
}
}
后记
📝 上篇精讲： 【算法题解】 Day21 查找
💖 我是 𝓼𝓲𝓭𝓲𝓸𝓽，期待你的关注；
👍 创作不易，请多多支持；
🔥 系列专栏： 算法题解
