白筱汐

想都是问题,做都是答案

0%

从上到下打印二叉树

前言

从上到下打印二叉树,是剑指offer上的经典题。该系列有3到题,实际上是对于二叉树的广度优先遍历问题的延伸。

剑指Offer 32 - I

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

解析:从上到下逐层打印,实际上就是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
37
38
// 构建二叉树
class TreeNode {
constructor(val) {
this.val = val;
this.left = null;
this.right = null;
}
}

const a = new TreeNode(3);
const b = new TreeNode(9);
const c = new TreeNode(20);
const d = new TreeNode(15);
const e = new TreeNode(7);
a.left = b;
a.right = c;
c.left = d;
c.right = e;

function levelOrder1(root) {
if (!root) {
return [];
}
const queue = [root];
const res = [];
while (queue.length) {
// 出队,获取队头节点
const n = queue.shift();
res.push(n.val);
if (n.left) {
queue.push(n.left);
}
if (n.right) {
queue.push(n.right);
}
}
return res
}

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

解析: