摘要:题目描述请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推分析第一反应可以按照普通的层次遍历然后再把第等等偶数层的结果翻转一下,但是那样子效率太低。
题目描述
请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推
分析第一反应可以按照普通的层次遍历然后再把第2、4、6等等偶数层的结果翻转一下,但是那样子效率太低。
上网查阅可以使用双向队列,即两头都可以进和出。需要从左到右打印的从队列头部进入和弹出,需要从右往左打印的从队列尾部进入和弹出
</>复制代码
/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
function Print(r)
{
if(r === null)
return [];
var ds = [];
var dir = "r";
var res = [];
ds.unshift(null);
ds.unshift(r);
while(ds.length > 1) {
var temp = [];
if(dir === "r"){
var cur = ds.shift();
while(cur !== null) {
temp.push(cur.val);
if(cur.left !== null)
ds.push(cur.left);
if(cur.right !== null)
ds.push(cur.right)
cur = ds.shift();
}
ds.unshift(null);
}else{
var cur = ds.pop();
while(cur !== null){
temp.push(cur.val);
if(cur.right !== null)
ds.unshift(cur.right);
if(cur.left !== null)
ds.unshift(cur.left);
cur = ds.pop();
}
ds.push(null);
}
res.push(temp);
dir = dir === "r" ? "l" : "r";
}
return res;
}
module.exports = {
Print : Print
};
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/96178.html
摘要:题目描述从上往下打印出二叉树的每个节点,同层节点从左至右打印。分析二叉树的层次遍历,可以借助队列的帮助实现 题目描述 从上往下打印出二叉树的每个节点,同层节点从左至右打印。 分析 二叉树的层次遍历,可以借助队列的帮助 实现 /* function TreeNode(x) { this.val = x; this.left = null; this.right =...
摘要:递归解法由于层次遍历的递归解法不是主流,因此只介绍前三种的递归解法前序遍历递归递归中序遍历递归递归后序遍历递归递归三种递归遍历的总结递归终止的条件为碰到空节点。 目录 分析二叉树的前序,中序,后序的遍历步骤 1.层序遍历 方法一:广度优先搜索 (以下解释来自leetcode官方题解) 方法...
摘要:题目描述输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。思路二叉树的大多数问题可以使用递归来解决,本题亦如此。 题目描述 输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。 思路 二叉树的大多数问题可以使用...
摘要:题目从上到下按层打印二叉树,同一层结点从左至右输出。分析分层次遍历肯定要使用队列来完成了,没啥好分析的代码实现 题目 从上到下按层打印二叉树,同一层结点从左至右输出。每一层输出一行。 分析 分层次遍历肯定要使用队列来完成了,没啥好分析的 代码实现 /* function TreeNode(x) { this.val = x; this.left = null; ...
阅读 3792·2021-11-11 11:00
阅读 2258·2021-10-08 10:05
阅读 3008·2021-10-08 10:04
阅读 3297·2021-09-30 09:48
阅读 4014·2021-09-27 14:10
阅读 1799·2021-09-09 09:33
阅读 2227·2019-08-30 15:55
阅读 1672·2019-08-30 13:53