首页 > 试题广场 >

按之字形顺序打印二叉树

[编程题]按之字形顺序打印二叉树
  • 热度指数:537973 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个二叉树,返回该二叉树的之字形层序遍历,(第一层从左向右,下一层从右向左,一直这样交替)

数据范围:,树上每个节点的val满足
要求:空间复杂度:,时间复杂度:
例如:
给定的二叉树是{1,2,3,#,#,4,5}

该二叉树之字形层序遍历的结果是
[
[1],
[3,2],
[4,5]
]
示例1

输入

{1,2,3,#,#,4,5}

输出

[[1],[3,2],[4,5]]

说明

如题面解释,第一层是根节点,从左到右打印结果,第二层从右到左,第三层从左到右。     
示例2

输入

{8,6,10,5,7,9,11}

输出

[[8],[10,6],[5,7,9,11]]
示例3

输入

{1,2,3,4,5}

输出

[[1],[3,2],[4,5]]

说明:本题目包含复杂数据结构TreeNode,点此查看相关信息
头像 牛客786963925号
发表于 2021-07-08 16:06:11
精华题解 解法一:使用队列 据题意,需要按照每一层的方式打印二叉树,因此较为直接的解法为「层次遍历」。 二叉树的层次遍历通过队列实现较为方便,步骤如下: 初始情况,根结点入队列; 定义变量size记录当前队列长度; 对于「当前队列」,遍历其所有元素:依次出队列、访问该元素、左右孩子入队列。注意:新入队列的「 展开全文
头像 牛客题解官
发表于 2022-04-22 11:52:19
精华题解 题目的主要信息: 给定一个二叉树,返回该二叉树的之字形层序遍 第一层从左向右,下一层从右向左,一直这样交替 举一反三: 学习完本题的思路你可以解决如下题目: BM26. 求二叉树的层次遍历 BM35. 判断是否是完全二叉树 方法一:非递归层次遍历(推荐使用) 知识点:队列 队列是一种仅支持在表尾 展开全文
头像 Maokt
发表于 2021-07-09 09:37:45
精华题解 算法思想一:层次遍历+栈 解题思路: 主要利用层次遍历二叉树的节点,并根据奇偶层添加二叉树的节点 算法流程: 1、特殊情况:如果树的根节点为空,则直接返回 【】 2、初始化:返回列表 res ,二叉树层索引 index,辅助栈 3、层次遍历循环 当栈为空跳出: 展开全文
头像 江南好___
发表于 2021-07-13 22:57:30
精华题解 描述 题目描述 请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。 示例 输入:{8,6,10,5,7,9,11} 返回值:[[8],[10,6],[5,7,9,11]]知识点:二叉树,队列,栈,BFS难度 展开全文
头像 qiaoHaoTing
发表于 2020-03-22 02:26:43
看了题解,没有思路跟我一样的,就补一个,哈哈哈哈哈哈如图 import java.util.Queue; import java.util.LinkedList; import java.util.Stack; public class Solution { public ArrayLis 展开全文
头像 少年又年少
发表于 2019-12-06 10:07:19
实现思路: 主要的方法与BFS写法没什么区别 BFS里是每次只取一个,而我们这里先得到队列长度size,这个size就是这一层的节点个数,然后通过for循环去poll出这size个节点,这里和按行取值二叉树返回ArrayList<ArrayList<Integer>>这种题 展开全文
头像 牛客题解官
发表于 2020-06-01 16:50:41
题目的主要信息: 给定一个二叉树,返回该二叉树的之字形层序遍 第一层从左向右,下一层从右向左,一直这样交替 举一反三: 学习完本题的思路你可以解决如下题目: JZ32. 从上往下打印二叉树 JZ78. 把二叉树打印成多行 方法一:非递归层次遍历(推荐使用) 知识点:队列 队列是一种仅支持在表尾进 展开全文
头像 SunnyX
发表于 2020-02-21 00:17:55
//解题思路:其实就是二叉树的层级遍历,不过是在遍历的时候,需要将偶数层的节点逆序。 //关键点:每次只处理上次在queue中剩余的节点,这是上一层的所有节点。 // 处理完后刚好将下一层的所有节点(包含null)又全部放了进去。 public ArrayList 展开全文
头像 ccจุ๊บ
发表于 2020-02-18 21:15:26
思路: 两个列表保存当前层和下一层,奇偶数决定正序打印还是逆序打印 class Solution: def Print(self, pRoot): # write code here if not pRoot: return [] 展开全文
头像 青杨风2199
发表于 2020-03-13 17:35:09
方法1:使用一个队列(用于层次遍历:所有层),加一个栈(用于高效翻转:偶数层) import java.util.ArrayList; import java.util.Stack; public class Solution { public ArrayList<ArrayList 展开全文
头像 冰梦IceDream
发表于 2019-09-10 09:08:04
实现思路:这道题其实就是从上到下分行打印二叉树的升级版本。只消定义一个变量来判断当前行是奇数行还是偶数行。(假设二叉树的第一行为0,即偶数行)。构造一个临时数组容器temp,存放二叉树中每一行的节点。如果为奇数行,就使用栈来存储(push方法),如果为偶数行,就使用队列来存储(unshift方法)。 展开全文
头像 Hakunamatata_Ryan
发表于 2021-10-15 13:16:55
import java.util.ArrayList; /* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int 展开全文
头像 牛錁007
发表于 2022-03-04 15:50:44
先求二叉树的层序遍历,再对数组下标对2求余数,余数不为0 就把数组元素饭庄reverse();返回arr。 /* function TreeNode(x) { this.val = x; this.left = null; this.right = null; } */ fu 展开全文
头像 不刷题就会白给
发表于 2020-03-03 21:52:04
这题其实就是把“二叉树打印成多行”的偶数层反转一下,搞个Collections.reverse(list);就可以了 二叉树打印成多行的地址:https://blog.nowcoder.net/n/0f27800916264398bc7e4c5c16191009 import java.util.* 展开全文