我要招人

去企业版

首页 > 试题广场 >

按之字形顺序打印二叉树

[编程题]按之字形顺序打印二叉树

热度指数：538078 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）

数据范围： $0 \le n \le 1500$ ,树上每个节点的val满足 $|val| <= 1500$
要求：空间复杂度： $O(n)$ ，时间复杂度： $O(n)$

例如：
给定的二叉树是{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.* 展开全文

问题信息

栈队列树

难度：

1524条回答 1793收藏 118755浏览

通过挑战的用户

想回学校的大魔...

2023-01-12 22:08:17
牛客12398...

2023-01-11 21:14:57
帮内推快手

2022-12-12 21:29:50
想吃荔枝

2022-10-23 14:44:12
那就开摆

2022-09-18 22:39:57

按之字形顺序打印二叉树

输入

输出

说明

输入

输出

输入

输出

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

问题信息

热门推荐

通过挑战的用户

相关试题