【算法专栏】从上到下打印二叉树
本系列是《剑指offer》或leetcode的JavaScript版本。 每期1-2个算法，也有可能是一个类别。 文章包括题目、思路以及代码。
题目1-不分行从上到下打印
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
思路
- 在打印第一行时，将左孩子节点和右孩子节点存入一个队列里
- 队列元素出队列打印，同时分别将左孩子节点和右孩子节点存入队列
- 这样打印二叉树的顺序就是没行从左到右打印
代码
function PrintFromTopToBottom(root) { const result = []; const queue = []; if (root) { queue.push(root); while (queue.length > 0) { const current = queue.shift(); if (current.left) { queue.push(current.left); } if (current.right) { queue.push(current.right); } result.push(current.val); } } return result; }题目2-按之字形顺序打印二叉树
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
思路
奇数从左到右，偶数从右到左
和上面的题目类似，同样可以借助在打印一层的时候填充下一层的方法
- 若当前层为奇数层，从左到右打印，同时填充下一层，从右到左打印（先填充左孩子节点再填充右孩子节点）。
- 若当前层为偶数层，从右到左打印，同时填充下一层，从左到右打印（先填充右孩子节点再填充左孩子节点）。
- 不难发现，我们可以使用栈来作为存储结构。
- 分别设定一个奇数栈和一个偶数栈， 从将二叉树头部元素存入奇数栈开始。
代码
function Print(root) { const result = []; const oddStack = []; const evenStack = []; let temp = []; if (root) { oddStack.push(root); while (oddStack.length > 0 || evenStack.length > 0) {
while (oddStack.length > 0) { const current = oddStack.pop(); temp.push(current.val); if (current.left) { evenStack.push(current.left); } if (current.right) { evenStack.push(current.right); } } if (temp.length > 0) { result.push(temp); temp = []; }
while (evenStack.length > 0) { const current = evenStack.pop(); temp.push(current.val); if (current.right) { oddStack.push(current.right); } if (current.left) { oddStack.push(current.left); } } if (temp.length > 0) { result.push(temp); temp = []; }
} } return result; }考察点
- 二叉树
- 栈
- 队列
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2019-04-02，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
