大家好,我是程序员吴师兄,欢迎来到 图解剑指 Offer 结构化专栏,在这个专栏里我将和大家一起学习如何用结构化的思维来思考、解题、写代码,希望能帮助你即使在面试的时候紧张也能做对。
AlgoMooc 算法慕课网,每道题目都有动画和图片,致力于帮助每个程序员通过算法面试!
今天分享的题目来源于 LeetCode 上的剑指 Offer 系列面试题 32 – I. 从上到下打印二叉树。
题目汇总链接:https://www.algomooc.com/jianzhioffer
一、题目描述
从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。
例如:
给定二叉树: [3,9,20,null,null,15,7]。
返回:
[3,9,20,15,7]
提示:
- 节点总数 <= 1000
二、题目解析
这道题实质是考查树的层次遍历(广度优先遍历)算法:
每一次打印一个结点的时候,如果该结点有子结点,则把该结点的子结点放到一个队列的末尾。接下来到队列的头部取出最早进入队列的结点,重复前面的打印操作,直至队列中所有的结点都被打印出来为止。
三、动画描述
隐藏内容
此处内容需要权限查看
会员免费查看四、图片描述
五、参考代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
class Solution {
public int[] levelOrder(TreeNode root) {
// 根节点为空的情况返回空数组
if (root == null) return new int[0];
// 生成一个队列,用来保存节点
Queue<TreeNode> queue = new LinkedList<>();
// 生成一个 list,用来保存输出的节点
List<Integer> list = new ArrayList<>();
// 首先让根节点入队
queue.add(root);
// 遍历队列,直到队列为空
while (!queue.isEmpty()) {
// 获取队列的头部元素
TreeNode node = queue.poll();
// 把结点值存放到 list 中
list.add(node.val);
// 判断该节点是否有左右子节点
// 如果左子节点有值,则把左子节点加入到队列中
if (node.left != null){
queue.add(node.left);
}
// 如果右子节点有值,则把右子节点加入到队列中
if (node.right != null){
queue.add(node.right);
}
}
// 根据题目要求,把 list 转化为数组
int[] res = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
res[i] = list.get(i);
}
// 返回 res
return res;
}
}
六、复杂度分析
时间复杂度
时间复杂度为 O(N)。
空间复杂度
空间复杂度为 O(N)。
七、相关标签
- 广度优先搜索
- 二叉树