剑指offer - 从上到下打印二叉树 - JavaScript
剑指offer - 从上到下打印二叉树 - JavaScript
心谭博客
发布于 2020-04-21 15:25:58
发布于 2020-04-21 15:25:58
题目描述: 从上往下打印出二叉树的每个节点，同层节点从左至右打印。
题目描述
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
解法：借助队列
需要使用一个队列来存储有用的节点。整体的思路如下：
- 将 root 放入队列
- 取出队首元素，将 val 放入返回的数组中
- 检查队首元素的子节点，若不为空，则将子节点放入队列
- 检查队列是否为空，为空，结束并返回数组；不为空，回到第二步
时间复杂度和空间复杂度是 O(N)。代码实现如下：
// ac地址：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/
// 原文地址：https://xxoo521.com/2020-02-02-btree-level-travel/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var levelOrder = function(root) {
if (!root) {
return [];
}
const data = [];
const queue = [root];
while (queue.length) {
const first = queue.shift();
data.push(first.val);
first.left && queue.push(first.left);
first.right && queue.push(first.right);
}
return data;
};在 Js 中没有专门的“队列”，都使用数组来实现。队列的常用操作：
- 入队：
array.push(val) - 出队：
array.shift() - 查看队首元素：
array[0] - 检查是否为空：
!!array.length
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-02-02，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录