前言
从上到下打印二叉树,是剑指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 }
|
从上到下按层打印二叉树,同一层的节点按从左到右的顺序打印,每一层打印到一行。
解析: