- 当前位置：首页 >综合 >字节一次面试，被二叉树的层序遍历捏爆了！
字节一次面试，被二叉树的层序遍历捏爆了！
发布时间：2025-11-05 15:45:48 来源：云智核 作者：IT科技
前言
大家好，字节我是次面叉树bigsai。
在数据结构与算法中，试被二叉树无论是序遍考研、笔试都是历捏非常高频的考点内容，在二叉树中，字节二叉树的次面叉树遍历又是非常重要的知识点，有个小老弟说他字节面试时候二叉树之字形打印紧张没写出来，试被力扣原题自己还写过很懊恼，序遍我也回想起自己刚学习时候那段"混乱的历捏"斗争，今天给大家讲讲二叉树的字节层序遍历。
前面介绍了二叉排序树的次面叉树构造和基本方法的实现，遍历也是试被比较重要的一环，并且二叉树的序遍层序遍历也是bfs的最简单情况，这里我就将二叉树的历捏层序遍历以及常考问题给大家分享一下。
在了解二叉树的遍历之前，b2b供应网需要具备数据结构与算法有队列、递归、栈、二叉树，这些内容咱们前面都有讲过，有这方面知识欠缺的同学可以往前翻一翻看一看!
层序遍历
层序遍历，听名字也知道是按层遍历。一个节点有左右节点，按层处理就是当前层兄弟节点的优先级要大于子节点处理的优先级，所以就是要将子节点放到后面处理，这就适合队列这个数据结构用来存储。
对于队列，先进先出。从root节点push到队列，那么队列中先出来的顺序是第二层的左右(假设都有)，第二层每个节点执行的时候按照左右顺序添加到队列，第三层的节点就会有序的放到最后面……按照这样的规则就能得到一个层序遍历的顺序。
实现的代码也很容易理解：
public int[] levelOrder(TreeNode root) { int arr[]=new int[10000]; int index=0; Queue<TreeNode>queue=new ArrayDeque<>(); if(root!=null) queue.add(root); while (!queue.isEmpty()){ TreeNode node=queue.poll(); arr[index++]= node.val; if(node.left!=null) queue.add(node.left); if(node.right!=null) queue.add(node.right); } return Arrays.copyOf(arr,index); }分层存储
但是云服务器提供商在具体笔试他可能要求你分层存储，例如力扣的102二叉树的层序遍历，要求返回一个List>类型。
这种相比上面一个多了一层逻辑就是每一层数据放到一块，这个也很容易，最好想到的就是两个队列(容器)一层一层遍历存储，然后交替，但是两个队列(容器)的写法常常会被面试官嫌弃，很多面试官让你想想怎么不用两个容器实现?
不用双队列去枚举结果也很容易，重要的就是先记录队列大小size(当前层节点数量)，然后执行size次数的枚举即可，具体代码为：
public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>>list=new ArrayList<List<Integer>>(); if(root==null)return list; Queue<TreeNode>q1=new ArrayDeque<TreeNode>(); q1.add(root); while (!q1.isEmpty()) { int size=q1.size(); List<Integer>value=new ArrayList<Integer>(); for(int i=0;i<size;i++) { TreeNode pNode=q1.poll(); if(pNode.left!=null) q1.add(pNode.left); if(pNode.right!=null) q1.add(pNode.right); value.add(pNode.val); } list.add(value); } return list; }之字形(锯齿形)打印
除了这个直接层序遍历，二叉树还有很高频的就是之字形遍历，例如剑指offer32和力扣103 二叉树的锯齿形层序遍历，它的题目要求为：
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，服务器托管第三行再按照从左到右的顺序打印，其他行以此类推。
这道题虽然不是难题，但是有点绕，本来队列这玩意我们就要大脑想一下什么顺序，又出来一个之字形(锯齿形状)，属实增加的思维逻辑，有不少小伙伴反映当时面试官让手撕这道题，自己以前明明写过，但是太紧张自己给自己绕进去了!
其实这个问题也很容易转化，因为值只是存储，我们按照老样子去进行层序遍历，只不过在遍历时候通过当前层奇偶数来给它判断是从左往右存储到结果中还是从右往左放到结果中。当然，判断奇数偶数也很容易，可以用变量，也可以用结果List的size()都可。
个人实现的一个朴素代码为：
public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> value=new ArrayList<>();//存储到的最终结果 if(root==null) return value; int index=0;//判断 Queue<TreeNode>queue=new ArrayDeque<>(); queue.add(root); while (!queue.isEmpty()){ List<Integer>va=new ArrayList<>();//临时 用于存储到value中 int len=queue.size();//当前层的数量 for(int i=0;i<len;i++){ TreeNode node=queue.poll(); if(index%2==0) va.add(node.val); else va.add(0,node.val); if(node.left!=null) queue.add(node.left); if(node.right!=null) queue.add(node.right); } value.add(va); index++; } return value; }上面实现代码也仅使用一个队列，不过这个问题可能有很多更巧妙的解法需要大家自己去挖掘。
结语
二叉树的层序遍历是二叉树内容中较为简单的内容，但是层序遍历尤其是之字形遍历(锯齿形遍历)出现的频率真的太高了，并且最好是掌握比较好的方法不要显得太臃肿。
不过在实际遇到问题时候，能AC是第一位，然后才是精简的逻辑和骚气的代码，总结一下就是队列实现层序，巧用size()实现一个容器枚举，奇偶判断实现之字形(锯齿形)遍历!也还算easy!
二叉树层序遍历变种问题不多，掌握上面三个问题基本就够了，而二叉树的前序、中序、后序遍历(递归非递归)考察非常多，后面会给大家加快梳理总结，敬请期待!
- 决斗链接电脑认证错误的解决方法（解决决斗链接电脑认证错误的有效途径）
- iPhone632GB如何满足现代人的手机需求？（一款性能稳定、容量适中的经典选择）
- 如何强制开机iPhone？（掌握关键操作，解决开机问题）
- 美图M8手机电量表现如何？（美图M8电池续航表现及充电速度详解）
- Pro6Plus信号表现如何？（探索Pro6Plus手机信号强弱的原因和解决方法）
- 解决电脑自动关机问题的技巧（让你的电脑不再频繁自动关机）
- 手机使用技巧（掌握这些技巧，你的手机将快速退役）
- 苹果电脑如何安装双系统Windows系统的详细教程（从零开始，快速学会在苹果电脑上安装Windows系统）
- 探索MQD42CH/A的优势与特点（揭秘MQD42CH/A的强大功能及性能表现）
- 华硕笔记本如何进入BIOS模式（教你轻松进入华硕笔记本的BIOS模式）
- 以710独显2g怎么样？（深度评测，解锁性能潜力）
- U盘深度分区教程（轻松解决U盘容量不对、无法分区等问题）
- 制作装机光盘教程——轻松安装系统的利器（一步步教你制作装机光盘，告别繁琐安装过程）
- U盘深度分区教程（轻松解决U盘容量不对、无法分区等问题）
- 想知道在Linux中你正在使用的网卡是什么吗？ 在Linux中很容易就找出网卡的生产商。打开一个终端并输入下面的额命令：复制代码代码如下:sudo lshw -C network假如上面的命令不能在sudo下使用，那就别用 sudo 的特权模式。它的输出看上去有点奇怪但是很有用。复制代码代码如下: *-network description: Wireless interface product: BCM4360 802.11ac Wireless Network Adapter vendor: Broadcom Corporation physical id: 0 bus info: pci@0000:03:00.0 logical name: wlan0 version: 03 serial: 9c:f3:87:c1:5d:6a width: 64 bits clock: 33MHz capabilities: busmaster caplist ethernet physical wireless configuration: broadcast=yes driver=wl0 driverversion=6.30.223.248 (r487574) ip=192.168.1.23 latency=0 multicast=yes wireless=IEEE 802.11abg resources: irq:18 memory:b0600000-b0607fff memory:b0400000-b05fffff如你所见，我Macbook Air上的无线网卡是BCM4360，这是一款在Ubuntu下面很容易出现无法检测无线网络问题的网卡。lshw 命令实际上是用来列出硬件的，因此命令的名字是lshw。带上网络的选项后，就会只过滤出网络硬件了。了解网卡的其他方法另外你还可以使用lspci命令来显示PCI总线上的信息。你应该使用普通用户来运行这个命令。只需要在命令行下输入：复制代码代码如下: lspci命令的输出看上去想这样：复制代码代码如下: 00:00.0 Host bridge: Intel Corporation Haswell-ULT DRAM Controller (rev 09) 00:02.0 VGA compatible controller: Intel Corporation Haswell-ULT Integrated Graphics Controller (rev 09) 00:03.0 Audio device: Intel Corporation Haswell-ULT HD Audio Controller (rev 09) 00:14.0 USB controller: Intel Corporation 8 Series USB xHCI HC (rev 04) 00:16.0 Communication controller: Intel Corporation 8 Series HECI #0 (rev 04) 00:1b.0 Audio device: Intel Corporation 8 Series HD Audio Controller (rev 04) 00:1c.0 PCI bridge: Intel Corporation 8 Series PCI Express Root Port 1 (rev e4) 00:1c.1 PCI bridge: Intel Corporation 8 Series PCI Express Root Port 2 (rev e4) 00:1c.2 PCI bridge: Intel Corporation 8 Series PCI Express Root Port 3 (rev e4) 00:1c.4 PCI bridge: Intel Corporation 8 Series PCI Express Root Port 5 (rev e4) 00:1c.5 PCI bridge: Intel Corporation 8 Series PCI Express Root Port 6 (rev e4) 00:1f.0 ISA bridge: Intel Corporation 8 Series LPC Controller (rev 04) 00:1f.3 SMBus: Intel Corporation 8 Series SMBus Controller (rev 04) 02:00.0 Multimedia controller: Broadcom Corporation Device 1570 03:00.0 Network controller: Broadcom Corporation BCM4360 802.11ac Wireless Network Adapter (rev 03) 04:00.0 SATA controller: Marvell Technology Group Ltd. 88SS9183 PCIe SSD Controller (rev 14)这些命令会同时列出有线和无线的网卡。你应该注意到上面的输出中显示我的系统中没有有线网卡。因为我使用的是Macbook Air，它没有以太网端口
- 小王卡和大王卡（解析小王卡和大王卡的特点与优势，助您做出明智的选择）
- 舒尔蓝牙动铁耳机的音质与性能如何？（一探舒尔蓝牙动铁耳机的出色音质和卓越性能）
- 电脑A卡显卡解析（深入了解电脑A卡显卡的特点和优势）
- 腾龙15-30逆光功能全面解析（探索腾龙15-30逆光功能的特点和优势）
- 探索3D游戏的引人入胜效果（数字世界中的沉浸式体验）
随便看看
- Copyright © 2025 Powered by 字节一次面试，被二叉树的层序遍历捏爆了！,云智核 滇ICP备2023006006号-28sitemap