前言大家好，我是bigsai。在数据结构和算法中，二叉树无论是考研还是笔试，都是出现频率非常高的考试内容。在二叉树中，二叉树的遍历是一个非常重要的知识点。一个小哥在字节面试的时候说了二叉树的曲折。打印时紧张，没有写出来。我写原题的时候很生气。也回想起刚学时的“乱”斗争。今天给大家讲讲二叉树的序列遍历。前面介绍了二叉排序树的构造和基本方法的实现。遍历也是重要的一环，二叉树的层序遍历也是bfs最简单的情况。这里我会给出二叉树的层序遍历和常见问题。大家分享。在了解二叉树的遍历之前，需要先了解队列、递归、栈、二叉树等数据结构和算法。我们之前已经提到过这些内容。缺乏这方面知识的同学可以期待看看！Layersequence遍历layer-ordertraversal，看名字就知道是逐层遍历。一个节点有左节点和右节点，按层处理是指当前层的兄弟节点优先级高于子节点，所以子节点必须在后面处理，适合队列作为数据结构用于存储。对于队列，先进先出。从根节点push到队列中，那么队列中最先出来的顺序就是第二层的左右（假设都有），当第二层的每个节点执行时，加入到按照左右顺序排队，第三层的节点会有顺序放在最后...根据这个规则，可以得到一个层序遍历的序列。实现的代码也很容易理解：publicint[]levelOrder(TreeNoderoot){intarr[]=newint[10000];intindex=0;Queuequeue=newArrayDeque<>();if(root!=null)queue.添加（根）；同时（！queue.isEmpty（））{TreeNodenode=queue.poll（）；arr[index++]=node.val；if（node.left！=null）queue.add（node.left）；if(node.right!=null)queue.add(node.right);}returnArrays.copyOf(arr,index);}分层存储但是在具体的笔试中，他可能会要求你分层存储，比如102Likou的二叉树的序列遍历需要返回一个List>类型。这种逻辑和上面的相比，多了一层，就是把每一层的数据都拼成一块。这也很容易。最好能想到的是两个队列（容器）逐层遍历存储，然后交替，但是两个队列（容器）的写法往往被面试官拒绝。很多面试官让你想想没有两个容器怎么实现？不用双队列也很容易枚举结果。重要的是先记录队列大小（当前层的节点数），然后执行size次的枚举，具体代码为：publicList>levelOrder(TreeNoderoot){List>list=newArrayList>();if(root==null)returnlist;Queueq1=newArrayDeque();q1.add(root);while(!q1.isEmpty()){intsize=q1.size();Listvalue=newArrayList();for(inti=0;i>levelOrder(TreeNoderoot){List>value=newArrayList<>();//最后存储的结果if(root==null)returnvalue;intindex=0;//判断Queuequeue=newArrayDeque<>();queue.add(root);while(!queue.isEmpty()){Listva=newArrayList<>();//暂时用来存入值intlen=queue.size();//当前层数for(inti=0;i
