剑指 Offer 32 - III. 从上到下打印二叉树 III
题目
请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。
例如:
给定二叉树: [3,9,20,null,null,15,7]
,
3
/ \
9 20
/ \
15 7
返回其层次遍历结果:
[
[3],
[20,9],
[15,7]
]
提示:
节点总数 <= 1000
题解
这题是 从上到下打印二叉树II 的变种, 仍然是使用广度优先遍历(BFS)。 但是在遍历过程中,需要一个标志位isOrderLeft = true
(默认从左往右),来判断打印的方向,由于要么是从左往右,要么是从右往左,所以打印完第一层后需要对标志位取反isOrderLeft = !isOrderLeft
具体执行流程:
-
如果树的根节点为空,则直接返回
[]
。 -
初始化,声明结果数组
res = []
, 包含根节点的队列queue = [root]
, 表示打印方向从左往右isOrderLeft = true
, -
循环当队列为空时终止
-
新建一个临时数组
tmp = []
, 用于保留当层节点值 -
当前层循环,循环次数为当前层的节点数(即队列的长度)
- 出队, 队首元素出队,即
node = queue.shift()
- 添加节点值,
- 如果方向是从左往右 将
node.val
添加到res
末尾, 即res.push(node.val)
- 如果方向是从右往左,将
node.val
添加到res
头部, 即res.unshift(node.val)
- 如果方向是从左往右 将
- 添加左右子节点,当
node.left
和node.right
都不为空,将左右子节点添加到tmp
- 出队, 队首元素出队,即
-
方向取反,
isOrderLeft = !isOrderLeft
-
将当前结果
tmp
添加res
-
-
返回结果数组
res
即可
代码
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function(root) {
if (root == null) return [];
const res = [];
const queue = [root];
// 是否从左打印,
let isOrderLeft = true;
while(queue.length > 0) {
let qLen = queue.length;
let tmp = [];
for (let i = 0; i < qLen; i ) {
const node = queue.shift();
if (isOrderLeft) {
node && tmp.push(node.val);
} else {
node && tmp.unshift(node.val);
}
node.left && queue.push(node.left);
node.right && queue.push(node.right);
}
isOrderLeft = !isOrderLeft
res.push(tmp);
}
return res;
};
原题链接
剑指 Offer 32 - III. 从上到下打印二叉树 III
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhfhajaf
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13