Algorithm/Tip:

计算二叉树的最大深度？

递归解法：
二叉树的最大深度是左子树和右子树中深度最大的一个，所以要分别计算左右两个子树的深度，然后取其最大的一个。
当根节点为空时，则深度为 0；
使用递归时，继续递归的条件为，当前节点是否有子节点存在，如果存在继续递归，如果不存在子节点，则开始回归。初始时左右子树的深度都为0，每次返回时取左右子树最大深度加1，得到当前深度。

  1. public int maxDepth(TreeNode root) {
  2.     if(root == null){
  3.         return 0;
  4.     }
  5.     // 递归获取左子树的深度
  6.     int left = maxDepth(root.left);
  7.     // 递归获取右子树的深度
  8.     int right = maxDepth(root.right);
  9.     // 获取左右子树中深度最大的一个，然后 +1，得到当前的深度
  10.     return Math.max(left,right) + 1;
  11. }

Review/Share：

JVM Spec Chapter 2.5 2.6

运行时数据区域划分

JVM 在运行程序时定义各种的运行时数据区域。一些数据区域是在 JVM 启动时创建，并在 JVM 退出时销毁。另一些是数据区域是属于各个线程的。属于线程的数据区域，会在线程创建时创建，在线程销毁时销毁。

pc 寄存器(program counter Register)

JVM 支持多个线程同时运行。每个 JVM 线程都有属于自己的 pc(program counter) 寄存器。在任何时候， 每个 JVM 线程执行的都是单个方法的代码，即该线程的当前方法。如果方法不是 native 的，pc 寄存器会包含正在执行的 JVM 指令的地址。如果线程当前执行的方法是 native 的，JVM pc 寄存器的值是 undefined(未定义) 的。JVM 的 pc 寄存器的宽度足够宽，可以容纳特定平台上的 returnAddress 或者 native 指针。

JVM 栈 (Java Virtual Machine Stacks)

每个 JVM 线程都专有一个 JVM 栈(JVM 栈也会叫做 JVM 堆栈)，在线程创建时创建。每个 JVM 栈里保存的内容叫做 栈帧。线程每调用一个方法，都会有一个栈帧压入 JVM 栈，当方法执行完之后，栈帧就会弹出 JVM 栈，并销毁。栈帧里保存了方法的局部变量和部分计算结果，并且会参与到方法的执行和返回。JVM 栈除了将栈帧压入和弹出外，不会直接操作栈帧，栈帧有可能在堆中分配的内存。JVM 栈的内存可以不是连续的。

JVM 栈的大小不必是固定的，JVM 可以根据需求动态调整。JVM 也可以允许用户和程序制定 JVM 栈的初始大小，最大和最小限制。

JVM 有可能会抛出一下的异常：

  1. 如果线程计算时需要的 JVM 栈 超出了允许的范围，会抛出 StackOverflowError；
  2. 当 JVM 栈允许动态扩展，并且 JVM 栈尝试去扩展时，如果当前没有做够的内存用于扩展，或者无法为新线程提供做够的内存创建 JVM 栈时， JVM 会抛出 OutOfMemoryError 。

堆(Heap)

JVM 有一个可以与所有线程共享的堆。所有的类实例和数组都是在堆这一块数据区域分配的。
堆在 JVM 启动时创建。堆中的对象会通过自动内存管理系统(垃圾收集器)进行回收，对象内存没有特别明确的释放时机。JVM 不会指定特定的内存管理系统，我们可以根据需求来选择合适的内存管理策略。

堆可以是固定大小的，也可以根据计算需求动态扩展和收缩。堆的内存可以是不连续的。

堆的大小不必是固定的，JVM 可以根据需求动态调整。JVM 也可以允许用户和程序指定堆的初始大小，最大和最小限制。JVM 提供了配置堆的最大和最小内存的参数。

如果计算需求大于自动内存管理系统提供的内存，会抛出 OutOfMemoryError。

堆不是数据结构意义上的堆，数据结构上的堆是一种有序的树，而这里堆是动态内存分配意义上的堆，用于管理动态生命周期的内存区域。

方法区(Method Area)

JVM 的方法区可以在所有的线程之间共享。方法区保存了加载过的每个类的结构，例如运行时常量池，字段和方法数据，以及方法和构造函数的代码，包括用于类实例初始化以及接口初始化的特殊方法。

方法区是在 JVM 启动时创建的。虽然方法区是在逻辑上是堆的一部分，存在垃圾收集机制；但是可以通过简单的实现可以选择不进行垃圾收集或作压缩。JVM 虚拟机规范没有规定方法区的位置或用于管理已编译代码的策略。

方法区的大小不必是固定的，JVM 可以根据需求动态调整。JVM 提供了配置方法区最大和最小内存的参数。方法区的内存可以是不连续的。

如果无法给方法区提供足够的内存，会抛出 OutOfMemoryError 。

运行时常量池(Run-Time Constant Pool)

介绍运行时常量池之前，需要先了解一下 constant_pool 表。constant_pool 表是类文件结构中的一个表，constant_pool 表里的每一项也都是一个表。constant_pool 表中存放了两大类常量：字面量和符号引用。

  • 字面量：文本字符串，整数，浮点数等源码中的一个固定值；
  • 符号引用：类和接口的全限定名(包含包名的全路径)，字段的名称和描述符(字段的类型等)，方法的名称和描述符(参数类型，返回类型等)

运行时常量池是方法区的一部分，JVM 创建类和接口的时候就会创建该类或者接口的运行时常量池。运行时常量池是在表示的就是类文件中 constant_pool 表的运行时的表示形式。
在创建类或者接口时，如果构造运行时常量池需要的内存查过 JVM 方法区中可用的内存，就会抛出 OutOfMemory 异常。

native 方法栈(Natvie Method Area)

JVM 的实现可以使用传统的堆，即俗称的 C 堆栈来实现 native 方法。native 方法栈也可以使用诸如 C 语言之类的编程语言实现 JVM 指令集的解释器。如果 JVM 不需要加载 native 方法，也不依赖于常规的堆栈，那么 JVM 的实现就不需要提供 native 方法栈。

JVM 规范并不强制要求native 方法栈的大小，它的大小可以不必是固定的，JVM 可以根据需求动态调整。JVM 提供了配置方法区最大和最小内存的参数。

如果线程在计算中所需要的 native 方法栈请求的内存超过了其允许的范围，JVM 会抛出 StackOverflowError。
当 native 方法栈允许动态扩展，并且 native 方法栈尝试去扩展时，如果当前没有做够的内存用于扩展，或者无法为新线程提供做够的内存创建 native 方法栈时， JVM 会抛出 OutOfMemoryError 。

栈帧(Frames)

方法栈里压入的就是这个栈帧，栈帧里保存了方法的局部变量和部分计算结果，栈帧也会执行动态链接，返回方法的值，传递异常等内容。
每当执行一个方法时，就会创建一个新的栈帧；当方法执行完毕之后，栈帧就会销毁，不管方法正常执行完毕还是抛出异常，栈帧都会销毁。
一个线程对应一个 JVM 栈，一个JVM 栈对应一组栈帧，栈帧就是在 JVM 栈中申请的内存。每个栈帧都有属于自己的局部变量数组，自己的操作数栈，对当前类方法的运行时常量池的引用。

局部变量数组和操作数栈的大小在编译时就已经确定了。栈帧结构的大小取决于 JVM 的实现，在方法调用的同时给栈帧分配内存。

在当前运行的线程中，在任何时候只有一个栈帧是活跃的；该栈帧一般称为当前帧，其方法称为当前方法。定义当前方法的类是当前类。局部变量和操作数栈上的操作，通常会引用当前栈帧。

如果当前栈帧所在的当前方法，调用了另一个方法，则当前活跃的栈帧就会发生改变。当新调用一个方法时，会新创建一个栈帧；这时会将新调用的方法所在的栈帧会压入 JVM 栈顶。当方法返回之后，当前的栈帧会将方法的返回值传回上一栈帧。

局部变量

每个栈帧都有一个包含所有局部变量的数组；这个数组的长度在编译完成之后就已经确定了。

一个局部变量可以保存的类型有很多，包含 boolean，char，byte，short，int，float，引用和 returnAddress。一对局部变量可以保存 long 和 double 类型。局部变量是按索引来寻址的，索引是从 0 开始的整形。

long 和 double 占有两个连续的局部变量，它们的索引以两个局部变量的最小值为准。举例说明，存储在索引地址为 n 的局部变量，实际上占用的索引地址为 n 和 n+1，我们无法从 n+1 的地址加载内容，只能从索引 n 开始加载。

JVM 不要求 n 是偶数，long 和 double 的值，不要求在局部变量数组中进行64位对齐的。JVM 规范不会要求如何保留两个局部变量来表示这些值。

JVM 使用局部变量在执行方法时传递参数，方法的参数可以认为是局部变量。在 Java 中执行类方法时，会从局部变量从 0 开始传递参数；在调用实例方法时，局部变量索引0始终用于传递低调用实例方法的对象的引用。其它参数都从1开始，依次传递。

操作数栈(Operand Stacks)

每个栈帧都包含一个后进新出的栈，叫做操作数栈。操作栈的最大深度在编译完毕后就会确定。

栈帧的操作数刚创建时容量为空。JVM 提了一系列指令，会将常量、局部变量的值、字段加载到操作数栈。JVM 会提供一些列指令从操作数栈获取操作数。操作数栈还会用于传递给方法参数，以及接受方法的结果。

举个例子，JVM 提供了 iadd 指令，用来将两个 int 类型相加。它要求两个相加的 int 值需要的是已经压入操作数栈的前两个值。两个 int 值会被弹出操作数栈，把它们相加后，它们的和会被重新压入操作数栈。子运算可以嵌套在操作数堆栈上，从而生成用于嵌套计算的值。

操作数栈上的每个条目，可以保存 JVM 的任何类型，包括 long 和 double 类型。

操作数栈中的值都必须以正确的方式入栈。比如将两个 int 值压入栈，然后将它们认作是 long 。也不能使用 iadd 指令将两个 float 相加。JVM 一小部分指令可以用于将运行时数据区域作为原始值进行操作，而不考虑其特定的类型，比如 dup 和swap 。这些指令不可以用于修改或者分解某单个值。在通过类文件验证时，会对操作数堆栈进行限制。

在任何时间点，操作数栈都有相应的深度，其中 long 和 double 类型的值，会占用两个单位的深度，而其它的单位只能占用一个单位的深度。