面试 Q&A (二)

参考:

char = '中文' 可以通过编译么？

可以。

public class primitivetype {
  public static void main(String[] args) {
    char i = '中';
    System.out.println(i);
  }
}
复制代码

可以运行输出'中'

Java中的一个char采用的是Unicode编码集，占用两个字节，而一个中文字符也是两个字节，因此Java中的char是可以表示一个中文字符的。

但是在C/C++中由于采用的字符编码集是ASCII，只有一个字节，因此是没办法表示一个中文字符的。

Java中的char是否可以存储一个中文字符之理解字符字节以及编码集

char几个字节？存储中文的char是几个字节?

java中char类型固定占2个字节。（注：char类型也可以存储一个汉字）。

以utf8为例，utf8是一个变长编码标准，可以以1~4个字节表示一个字符，而中文占3个字节，ascII字符占1个字节。

那么为什么我们在java里面可以用一个char来表示一个中文呢？

因为java是以unicode作为编码方式的。unicode是一个定长的编码标准，每个字符都是2个字节，也就是1个char类型的空间。

在编译时会把utf8的中文字符转换成对应的unicode来进行传输运算。

String采用一种更灵活的方式进行存储。在String中，一个英文字符占1个字节，而中文字符根据编码的不同所占字节数也不同。在UTF-8编码下，一个中文字符占3个字节；而使用GBK编码时一个中文字符占2个字节。测试代码如下

中文并不一定是占两个字节的，具体占多少字节是跟具体的编码方式相关的。 比如说：GB2312、GBK、GB18030 编码是占用两个字节的，但是 UTF-8 编码的话至少需要占用三个字节。

解释一下MVC 以及 MVC Spring

MVC

MVC模式是软件工程中的一种软件架构模式，把软件系统分为三个基本部分：模型、视图和控制器。

mvc是一种建构网站的方法或思想，设计理念。mvc不是框架,而框架是基于mvc思想。

在早期java web，主要使用jsp + java bean模式，jsp与java bean产生严重耦合。出现了前端后端相互依赖的问题。

于是出现了servlet + jsp + java bean。 servlet是controller jsp是view 各自java bean 是model 对于后端来说，由于控制器和模型层的分离使得许多代码可以重用。 mvc的经典框架 struts1/struts2和作为模型层的hibernate纷纷出现。

• springmvc中传统的模型层被拆分成业务层service和数据访问层dao。
• 在service下可以通过spring的声明式事务操作数据访问层，而在业务层还允许访问nosql。
• Spring MVC通过一套MVC注解,让POJO普通java类成为处理请求的控制器，而无需实现任何接口。
• 支持REST风格的URL请求
• 采用松散耦合可插拔组件结构,比其他MVC框架更具扩展性和灵活性

spring mvc组件和流程图

执行原理

1. spring mvc将所有的请求都提交给DispatcherServlet,它会委托应用系统的其他模块负责对请求 进行真正的处理工作。
2. DispatcherServlet查询一个或多个HandlerMapping,找到处理请求的Controller.
3. DispatcherServlet请请求提交到目标Controller
4. Controller进行业务逻辑处理后，会返回一个ModelAndView
5. Dispathcher查询一个或多个ViewResolver视图解析器,找到ModelAndView对象指定的视图对象
6. 视图对象负责渲染返回给客户端。

• 用户发起请求到前端控制器（Controller）
• 前端控制器没有处理业务逻辑的能力，需要找到具体的模型对象处理（Handler），到处理器映射器（HandlerMapping）中查找Handler对象（Model）。
• HandlerMapping返回执行链，包含了2部分内容： ① Handler对象、② 拦截器数组
• 前端处理器通过处理器适配器包装后执行Handler对象。
• 处理业务逻辑。
• Handler处理完业务逻辑，返回ModelAndView对象，其中view是视图名称，不是真正的视图对象。
• 将ModelAndView返回给前端控制器。
• 视图解析器（ViewResolver）返回真正的视图对象（View）。
• (此时前端控制器中既有视图又有Model对象数据）前端控制器根据模型数据和视图对象，进行视图渲染。
• 返回渲染后的视图（html/json/xml）返回。
• 给用户产生响应。

在浏览器输入url发生了什么?

假如输入maps.google.com

1. 浏览器会检查dns记录缓存，找到url对应的ip地址

dns：domain name system 保存域名和连接的ip地址，每一个url都有唯一的ip地址。

为了找到dns记录，浏览器会依次检查以下4种缓存

• 检查浏览器缓存，浏览器为您以前访问过的网站维护一个固定期限的DNS记录存储库。因此，它是第一个运行DNS查询的地方。
• 浏览器检查系统缓存。如果在浏览器缓存中找不到，浏览器将向底层计算机OS发出系统调用(即Windows上的gethostname)以获取记录，因为OS还维护DNS记录的缓存。
• 检查路由器缓存。如果在你的电脑上找不到的话，浏览器就会与维护自己的DNS记录缓存的路由器进行通信。
• 它检查ISP缓存。如果所有的步骤都失败了，浏览器将转移到ISP。您的ISP维护它自己的DNS服务器，它包含一个DNS记录的缓存，浏览器将会检查找到您请求的URL的最后希望。

Internet Service Provider ，簡稱 ISP

2. 如果请求的URL不在缓存中，ISP的DNS服务器将发起一个DNS查询，以查找托管maps.google.com的服务器的IP地址。

为了让我的计算机连接到托管maps.google.com的服务器，我需要maps.google.com的IP地址。DNS查询的目的是在internet上搜索多个DNS服务器，直到找到网站的正确IP地址。这种类型的搜索被称为 递归搜索 ，因为搜索将在DNS服务器和DNS服务器之间重复进行，直到找到我们需要的IP地址，或者返回一个错误响应说无法找到它为止。

在这种情况下，我们将把ISP的DNS服务器称为DNS递归器，它的职责是通过询问internet上的其他DNS服务器来找到想要的域名的正确IP地址。其他DNS服务器称为名称服务器，因为它们基于网站域名的域架构执行DNS搜索。

3. 浏览器启动与服务器的TCP连接

HTTP协议即超文本传送协议(Hypertext Transfer Protocol )，是Web联网的基础，也是手机联网常用的协议之一，HTTP协议是建立在TCP协议之上的一种应用。

一旦浏览器接收到正确的IP地址，它将与匹配IP地址以传输信息的服务器建立TCP连接。三次握手。

为了在您的计算机(客户端)和服务器之间传输数据包，建立一个TCP连接非常重要。这个连接是通过一个叫做TCP/IP三方握手的过程建立的。这是一个三个步骤，其中客户端和服务器交换SYN(同步)和ACK(确认)消息来建立连接。

为了保证服务端能收接受到客户端的信息并能做出正确的应答而进行前两次(第一次和第二次)握手，为了保证客户端能够接收到服务端的信息并能做出正确的应答而进行后两次(第二次和第三次)握手。

4. 浏览器发送http请求

比如get请求 localhost:8080

Host: localhost:8080
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.13; rv:60.0) Gecko/20100101 Firefox/60.0
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8
Accept-Language: zh-CN,zh;q=0.8,zh-TW;q=0.7,zh-HK;q=0.5,en-US;q=0.3,en;q=0.2
Accept-Encoding: gzip, deflate
Cookie: JSESSIONID=8051806AE26B8CAB93BA03AC32A2191E; JSESSIONID=63AB1FE24ECF5F0930743468B802818B
Connection: keep-alive
Upgrade-Insecure-Requests: 1
Cache-Control: max-age=0
复制代码

5. 服务器处理请求并返回响应

该服务器包含一个web服务器(比如apache)。接收来自浏览器的请求并将其传递给请求处理程序以读取和生成响应。请求处理程序是一个程序(用php等编写)用于读取请求、其头部和cookies，以检查所请求的内容，并在需要时更新服务器上的信息。然后它将以特定的格式(JSON、XML、HTML)组装响应。

6. 服务器发送一个HTTP响应。

服务器响应包含您请求的web页面、状态代码、压缩类型(内容编码)、如何缓存页面(缓存控制)、要设置的任何cookie、隐私信息等。

HTTP/1.1 200 
Content-Type: text/html;charset=UTF-8
Content-Language: zh-CN
Content-Length: 97
Date: Wed, 04 Jul 2018 08:04:54 GMT
复制代码

状态码：

• 1xx代表一条信息
• 2xx说明访问成功
• 3xx将客户重定向到其他url
• 4xx客户端发生错误
• 5xx服务端发生错误状态码详细

7. 浏览器显示html内容

浏览器分阶段显示HTML内容。首先，它将呈现裸骨HTML骨架。然后，它将检查HTML标记并发出GET请求，请求web页面上的其他元素，如图像、CSS样式表、JavaScript文件等。这些静态文件被浏览器缓存，这样下次访问页面时就不必再取回它们了。最后，你会看到网页出现在你的浏览器上。

HashMap如何实现的？

• hashmap是基于哈希表即散列表的。

• hashmap通过hashCode方法计算hash值,hash值是通过key对象来计算。hash值用来找到存储Entry的正确位置。

• hashmap使用equals方法来查找在get()时要检索的键的值，并在put()时查找该键是否已经存在。

• 冲突意味着有多个键拥有同样的hash值，在这种情况下entry对象将会存储在了同一个linkedlist里。

  HashMap在java中使用内部 Node<K,V>来存储映射。HashMap基于散列算法，并在键上使用hashCode()和equals()方法进行get和put操作。

  HashMap使用单个链表来存储元素，这些元素称为bucket。当我们调用put方法时，将使用key的hashCode来确定存储映射的bucket。

  一旦确定了bucket，就使用hashCode检查是否已经有一个具有相同hashCode的键。如果存在一个具有相同hashCode的现有键，则在key上使用equals()方法。如果equals返回true，那么value将被覆盖，否则将对这个单独链接的list bucket创建一个新的映射。如果没有具有相同hashCode的键，则将映射插入到bucket中。

  hashmap 有一个表

  **
  * The table, resized as necessary. Length MUST Always be a power of two.
  */
  
     transient Node<K,V>[] table;
  复制代码

static class Node<K,V> implements Map.Entry<K,V> {
      final int hash;
      final K key;
      V value;
      Node<K,V> next;

      Node(int hash, K key, V value, Node<K,V> next) {
          this.hash = hash;
          this.key = key;
          this.value = value;
          this.next = next;
      }

      public final K getKey()        { return key; }
      public final V getValue()      { return value; }
      public final String toString() { return key + "=" + value; }

      public final int hashCode() {
          return Objects.hashCode(key) ^ Objects.hashCode(value);
      }

      public final V setValue(V newValue) {
          V oldValue = value;
          value = newValue;
          return oldValue;
      }

      public final boolean equals(Object o) {
          if (o == this)
              return true;
          if (o instanceof Map.Entry) {
              Map.Entry<?,?> e = (Map.Entry<?,?>)o;
              if (Objects.equals(key, e.getKey()) &&
                  Objects.equals(value, e.getValue()))
                  return true;
          }
          return false;
      }
  }
复制代码

put方法,注意链表中是红黑树的实现

TreeNode节点,这个类有非常多的方法
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }
}
复制代码

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

    /**
     * Implements Map.put and related methods
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value
     * @param evict if false, the table is in creation mode.
     * @return previous value, or null if none
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
复制代码

GC过程,GC是在什么时候，对什么东西，做了什么事情?

gc需要完成的3件事情

• 什么时候回收？
• 哪些内存需要回收？
• 如何回收？

对堆进行回收之前首先要确定对象之中哪些还“存活”，哪些“死去”。

1. 引用计数算法

2. 可达性分析算法 这个算法的基本思路就是通过一系列的称为“GC Roots”的对象作为起始点，从这些节点开始向下搜索，搜索所走过的路径称为引用链（Reference Chain），当一个对象到GC Roots没有任何引用链相连（用图论的话来说，就是从GC Roots到这个对象不可达）时，则证明此对象是不可用的。

   

   在java中,可作为GC Roots的对象包括以下几种：

   • 虚拟机栈(栈帧中的本地变量表)中引用的对象
   • 方法区中类静态属性引用的对象
   • 方法区中常量引用的对象
   • 本地方法栈中JNI(Native方法)引用的对象。

强引用，软引用，弱引用，虚引用

Object obj=new Object（）

回收方法区(永久代)

永久代的垃圾回收主要回收两部分

• 废弃常量
• 无用的类：该类所有的实例都已经被回收,也就是java堆中不存在该类的任何实例，加载该类的ClassLoader已经被回收,该类对应的java.lang.Class对象没有在任何地方被引用，无法在任何地方通过反射访问该类的方法。
• 在大量使用反射、动态代理、CGLib等ByteCode框架、动态生成JSP以及OSGi这类频繁自定义ClassLoader的场景都需要虚拟机具备类卸载的功能，以保证永久代不会溢出。

垃圾收集算法

1. 标记-清除算法

最基础的收集算法,"mark-sweep"标记-清除算法。

算法分为“标记”和“清除”两个阶段：首先标记出所有需要回收的对象，在标记完成后统一回收所有被标记的对象，它的标记过程其实在前一节讲述对象标记判定时已经介绍过了。之所以说它是最基础的收集算法，是因为后续的收集算法都是基于这种思路并对其不足进行改进而得到的。

它的主要不足有两个：一个是 效率问题 ，标记和清除两个过程的效率都不高；另一个是 空间问题 ，标记清除之后会产生大量不连续的内存碎片，空间碎片太多可能会导致以后在程序运行过程中需要分配较大对象时，无法找到足够的连续内存而不得不提前触发另一次垃圾收集动作。

2. 复制算法

为了解决效率问题，一种称为“复制”（Copying）的收集算法出现了，它将可用内存按容量划分为大小相等的两块，每次只使用其中的一块。当这一块的内存用完了，就将还存活着的对象复制到另外一块上面，然后再把已使用过的内存空间一次清理掉。这样使得每次都是对整个半区进行内存回收，内存分配时也就不用考虑内存碎片等复杂情况，只要移动堆顶指针，按顺序分配内存即可，实现简单，运行高效。只是这种算法的代价是将内存缩小为了原来的一半，未免太高了一点。

新生代中的对象98%是“朝生夕死”的，所以并不需要按照1:1的比例来划分内存空间，而是将内存分为一块较大的 Eden空间 和 两块较小的Survivor空间 ，每次使用Eden和其中一块Survivor。当回收时，将Eden和Survivor中还存活着的对象一次性地复制到另外一块Survivor空间上，最后清理掉Eden和刚才用过的Survivor空间。HotSpot虚拟机默认Eden和Survivor的大小比例是8:1，也就是每次新生代中可用内存空间为整个新生代容量的90%（80%+10%），只有10%的内存会被“浪费”。当然，98%的对象可回收只是一般场景下的数据，我们没有办法保证每次回收都只有不多于10%的对象存活，当Survivor空间不够用时，需要依赖其他内存（这里指老年代）进行分配担保（Handle Promotion）。

内存的分配担保就好比我们去银行借款，如果我们信誉很好，在98%的情况下都能按时偿还，于是银行可能会默认我们下一次也能按时按量地偿还贷款，只需要有一个担保人能保证如果我不能还款时，可以从他的账户扣钱，那银行就认为没有风险了。内存的分配担保也一样，如果另外一块Survivor空间没有足够空间存放上一次新生代收集下来的存活对象时，这些对象将直接通过分配担保机制进入老年代。

3. 标记-整理法

标记过程仍然与“标记-清除”算法一样，但后续步骤不是直接对可回收对象进行清理，而是让所有存活的对象都向一端移动，然后直接清理掉端边界以外的内存。

4. 分代收集算法Generational Collection

只是根据对象存活周期的不同将内存划分为几块。一般是把Java堆分为新生代和老年代，这样就可以根据各个年代的特点采用最适当的收集算法。

在新生代中，每次垃圾收集时都发现有大批对象死去，只有少量存活，那就选用复制算法，只需要付出少量存活对象的复制成本就可以完成收集。

而老年代中因为对象存活率高、没有额外空间对它进行分配担保，就必须使用“标记—清理”或者“标记—整理”算法来进行回收。

垃圾收集器

如果说收集算法是内存回收的方法论，那么垃圾收集器就是内存回收的具体实现

Minor GC 和 Full GC

• 新生代GC（Minor GC）：指发生在新生代的垃圾收集动作，因为Java对象大多都具备朝生夕灭的特性，所以Minor GC非常频繁，一般回收速度也比较快。具体原理见上一篇文章。
• 老年代GC（Major GC / Full GC）：指发生在老年代的GC，出现了Major GC，经常会伴随至少一次的Minor GC（但非绝对的，在Parallel Scavenge收集器的收集策略里就有直接进行Major GC的策略选择过程）。Major GC的速度一般会比Minor GC慢10倍以上。

内存分配与回收策略

• 对象优先在Eden分配 大多数情况下，对象在新生代Eden区分配，等eden区没有足够空间进行分配，虚拟机将会发起一次Minor GC
• 大对象直接进入老年代 所谓大对象是指，需要大量连续内存空间的java对象，最典型的就是那种很长的字符串和数组。
• 长期存活的对象将进入老年代 为了确定哪些是老年代，虚拟机给每个对象定义了一个对象年龄计数器。对象在Survivor区中每熬过一次Minor GC年龄就增加1.
• 空间分配担保 在发生Minor GC之前，虚拟机会先检查老年代最大可用的连续空间是否大于新生代所有对象总空间，如果这个条件成立，那么Minor GC可以确保是安全的。如果不成立，则虚拟机会查看HandlePromotionFailure设置值是否允许担保失败。如果允许，那么会继续检查老年代最大可用的连续空间是否大于历次晋升到老年代对象的平均大小，如果大于，将尝试着进行一次Minor GC，尽管这次Minor GC是有风险的；如果小于，或者HandlePromotionFailure设置不允许冒险，那这时也要改为进行一次Full GC

什么时候发生回收？

eden满了minor gc，升到老年代的对象大于老年代剩余空间full gc，或者小于时被HandlePromotionFailure参数强制full gc；gc与非gc时间耗时超过了GCTimeRatio的限制引发OOM，调优诸如通过NewRatio控制新生代老年代比例，通过MaxTenuringThreshold控制进入老年前生存次数等

参考： icyfenix.iteye.com/blog/715301

数据库慢查询

慢sql特点 1 数据库CPU负载高。一般是查询语句中有很多计算逻辑，导致数据库cpu负载。 2 IO负载高导致服务器卡住。这个一般和全表查询没索引有关系。 3 查询语句正常，索引正常但是还是慢。如果表面上索引正常，但是查询慢，需要看看是否索引没有生效。

打开MySQL的慢查询日志来进一步定位问题。mysql提供了慢查询日志，日志会记录所有执行时间超过long_query_time的sql

要开启日志,需要在MySQL的配置文件的mysqlld项下配置慢查询日志开启。

有些SQL虽然出现在慢查询日志中，但未必是其本身的性能问题，可能是因为锁等待，服务器压力高等等。

需要分析SQL语句真实的执行计划，而不是看重新执行一遍SQL时，花费了多少时间，由自带的慢查询日志或者开源的慢查询系统定位到具体的出问题的SQL，然后使用Explain工具来逐步调优，了解 MySQL 在执行这条数据时的一些细节，比如是否进行了优化、是否使用了索引等等。基于 Explain 的返回结果我们就可以根据 MySQL 的执行细节进一步分析是否应该优化搜索、怎样优化索引。

总结

1. 打开慢日志查询，确定是否有SQL语句占用了过多资源，如果是，在不改变业务原意的前提下，对insert、group by、order by、join等语句进行优化。
2. 考虑调整MySQL的系统参数：innodb_buffer_pool_size、innodb_log_file_size、table_cache等。
3. 确定是否是因为高并发引起行锁的超时问题。
4. 如果数据量过大，需要考虑进一步的分库分表。

数据库inner join,left outer join,right outer join

两个表,customers,orders

customers

内部联结

orders

SELECT customers.cust_id,orders.order_num FROM customers INNER JOIN orders ON customers.cust_id = orders.cust_id;
复制代码

外部联结

SELECT customers.cust_id,orders.order_num FROM customers LEFT OUTER JOIN orders ON customers.cust_id = orders.cust_id
复制代码

SELECT customers.cust_id,orders.order_num FROM customers RIGHT OUTER JOIN orders ON customers.cust_id = orders.cust_id
复制代码

在使用 OUTER JOIN 语法时，必须使用 RIGHT 或 LEFT 关键字 指定包括其所有行的表( RIGHT 指出的是 OUTER JOIN 右边的表，而 LEFT 指出的是 OUTER JOIN 左边的表)。上面的例子使用 LEFT OUTER JOIN 从 FROM 子句的左边表(customers表)中选择所有行。为了从右边的表中选择所有行，应该使用 RIGHT OUTER JOIN .

解释一下索引

当表的数据量比较大时，查询操作会比较耗时。建立索引是加快查询速度的有效手段。数据库索引类似于图书后面的索引，能快速定位到需要查询的内容。

数据库索引有多种类型，常见索引包括 顺序文件上的索引 ， b+树索引 、 哈希索引 、 位图索引 、 全文索引 。

在mysql中，存储引擎先在索引中找到对应值，然后根据匹配的索引记录找到对应的数据行。

mysql先在索引上按值进行查找，然后返回所有包含该值的数据行。

索引可以包含一个或多个列的值。如果索引包含多个列，那么列的顺序也十分重要，因为mysql只能高效地使用索引的最左前缀列。

索引可以让服务器快速定位到表的指定位置 索引的优点：

1. 索引大大减少了服务器需要扫描的数据量
2. 索引可以帮助服务器避免排序和临时表
3. 索引可以让随机I/O变成顺序I/O

数据库优化

数据库优化总结

• 选取最适用的字段属性
• 使用join来代替子查询
• 使用联合union来代替手动创建的临时表
• 使用事务
• 锁定表

schema模式与数据类型优化

mysql支持的数据类型非常多，选择正确的数据类型对于获得高性能至关重要。不管存储哪种类型的数据，下面几个简单的原则都有助于作出更好选择。

• 更小，一般情况下尽量使用可以正确存储数据的最小数据类型。
• 简单就好，简单数据类型需要更少的cpu周期。
• 尽量避免null

使用索引

索引的代价：1.需要占硬盘空间 2.一旦插入新的数据，需要重新建索引 高性能索引策略

• 独立的列,独立的列”是指索引列不能是表达式的一部分，也不能是函数的参数
• 前缀索引和索引选择性
• 多列索引
• 选择合适的索引列顺序
• 聚簇索引

查询性能优化

优化数据访问

• 是否向数据库请求了不需要的数据
• • mysql是否扫描额外的记录
    • 查询消耗：响应时间，扫描的行数，返回的行数

重构查询的方式

优化服务器设置

操作系统和硬件优化

层次遍历

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        Queue<TreeNode> qp = new LinkedList<>();
        qp.offer(root);
        
        while(!qp.isEmpty()){
            List<Integer> level = new ArrayList<>();
            TreeNode node = null;
            int lenL = qp.size();
            for(int i = 0; i < lenL; i++){
                node = qp.poll();
                level.add(node.val);
                if(node.left != null){
                    qp.offer(node.left);
                }
                
                if(node.right != null){
                    qp.offer(node.right);
                }
            }
            res.add(level);
        }
        return res;
    }
}
复制代码