Algorithm/Tip:

判断两个树是否相同

给定两个数，判断两个树是否相同？最简单好理解的就是暴力 DFS 。
判断两个树是否相同的条件一般有如下几个：

  1. 都为空，树相同；
  2. 其中一个空，树不相同；
  3. 两个都是非空，但是 val 不相等，树不相同。

基于上面的三个条件下，我们可以通过 DFS 对比两个树的每一个 node ，只要符合所有的条件，则表示树相同

  1. public boolean isSameTree(TreeNode s, TreeNode t){
  2.     // 都为空，树相同
  3.     if(s == null && t == null){
  4.         return true;
  5.     }
  7.     // 其中一个为空，树不相同
  8.     if(s == null || t == null ){
  9.         return false;
  10.     }
  12.     // 两个非空，值不相同，树不相同
  13.     if(s.val != t.val){
  14.         return false;
  15.     }
  17.     // 递归两个树的所有 node,使每个 node 都经历上面的判断
  18.     return isSameTree(s.left, t.left) && isSameTree(s.right, t.right); 
  19. }

另一个树的子树

给定两个非空树 s 和 t ，判断 t 是否是 s 的子树。
判断 t 是否是 s 的子树，一般有如下几个条件：

  1. t 和 s 相同，那么 t 是 s 子树成立；
  2. t 是 s 的左子树，或者是左子树的中的其它子树；
  3. t 是 s 的右子树，或者是右子树的中的其它子树。

上面的 2,3 条件只要符合一种就能认定 t 是 s 的子树。我们又可以分解一下:
t 是 s 的左/右子树，或者是左/右子树的中的其它子树，可以认为我们需要判断 t 和 s 的左/右子树某一个子树相同，这样我们就可以将上面的问题简化成判断 t 和 s 的某一个子树是否相同，回到了上面的判断两个树是否想同的问题。

基于上面的条件，我们依然使用 DFS 暴力比较：

  1. public boolean isSubtree(TreeNode s, TreeNode t) {
  2.     if(s == null){
  3.         return false;
  4.     }
  5.     if(isSameTree(s, t)){
  6.         return true;
  7.     }else{
  8.         return isSubtree(s.left, t) || isSubtree(s.right, t);
  9.     }
  10. }

对称二叉树

给定一个二叉树，判断该树是否是一个镜像对称的二叉树。
下面这个二叉树就是对称的，

  1.         1 
  2.    / \
  3.   2   2
  4.  / \ / \
  5. 3  4 4  3

下面这个二叉树不是对称的，

  1.         1
  2.    / \
  3.   2   2
  4.    \   \
  5.    3    3

判断一个二叉树是否是对称的，一般都需要以下几个条件:

  1. 如果根节点为 null ,则是对称的；
  2. 左子树和右子树都为空，则是对称的；
  3. 左子树或者右子树为空，则是不对称的；
  4. 除去上面的条件，在同层级中，对于同一个位置，左子树中任意节点等于右子树中的值；

根据上面的条件，也可以转换为判断两个树是否相等的问题，只是对比的是左子树的左节点与右子树的右节点。

  1. public boolean isSymmetric(TreeNode root) {
  2.     if(root == null){
  3.         return true;
  4.     }
  6.     return check(root.left,root.right);        
  7. }
  9. boolean check(TreeNode left,TreeNode right){
  10.     if(left == null && right == null){
  11.         return true;
  12.     }
  14.     if(left == null || right == null){
  15.         return false;
  16.     }
  18.     if(left.val != right.val){
  19.         return false;
  20.     }
  21.     // 递归判断左右节点时，需要对比左子树左节点的值对比右子树右节点的值
  22.     return check(left.left, right.right) && check(left.right,right.left);
  23. }

Review/Share

JVM Spec Chapter 2.6 2.7 2.9 2.10

栈帧(Frames)

动态链接

为了支持方法代码的动态链接，每个栈帧都包含了在运行时常量池中的当前方法的类型引用。调用类文件引用的方法，需要通过符号引用调用，变量的访问也需要通过符号引用。动态链接会将这些 方法的符号引用 转换成实际的方法引用，避免出现在加载的类中出现未定义的符号，并在运行时将变量访问权限偏移量转换成在相关联的存储结构中的偏移量。
这种后期绑定的方法和变量的方式，可以避免在其它类中修改它的可能。

方法的正常调用完成

如果方法调用过程中没有抛出异常，就算是直接从 JVM 显式执行 throw 语句的结果， 方法调用都算正常完成。如果当前方法的调用正常完成，方法就可能会有有一个返回结果。方法的返回执行的是 return 指令，当然其返回的类型必须适合当前方法的返回值类型。
在这种情况下，当前栈帧用于恢复调用者的状态，包含它的局部变量和操作数栈，调用者的程序计数器(program counter)会适当的递增以跳过该方法的调用指令；然后在调用方法的栈帧中正常执行，并将返回值压入到该栈帧的操作数栈上。

方法的突然的调用完成

如果方法内的 JVM 指令执行导致 JVM 抛出异常，并且该异常未在该方法的内处理，则说该方法的调用突然完成。执行 athrow 指令也会显示的抛出异常，如果当前方法没有抛出异常，就会导致方法突然完成。方法突然调用完成不会给调用者返回结果。

对象的表示

JVM 不强制要求对象的任何特定的内部结构。
在 Oracle 的一些 JVM 的实现中，类的实例的引用是一个句柄的指针，这个句柄本身也是一对指针，其中一个是指向包含对象方法的表，指向表示对象类型的 Class 对象的指针；另一个是指向从堆中为对象数据分配的内存。

浮点运算省略

特殊方法

在 JVM 层级，每个 Java 语言写的构造方法，都会对应一个叫做 <init> 特殊名字的实例初始化方法。在 Java 中 <init> 不是一个有效的标识符，它是在编译后生成的，在 JVM 上使用的特殊的实例化方法。实例初始化方法只能在 JVM 中使用 invokespecial 指令执行，并且它只能在未初始化的实例上执行。实例初始化方法的访问权限是跟派生出它的父类的的构造函数的权限一样。

一个类或者接口最多有一个初始化方法，并通过它进行初始化。如果构造函数是无参的，在编译后就换转换成 <clinit> 。

在 Java7 及以上版本，要求在 clinit 额外添加 ACC_STATIC 修饰符，这样才能称为类或者接口的初始化方法。

跟 <init> 类似， <clinit> 方法是由编译器提供的。在 Java 语言中它不是一个合法的标识符，不能在 Java 中直接使用。类和接口的初始化方法由 JVM 隐式调用的，而不是执行 JVM 指令，而是作为类初始化的一部分间接调用。

满足一下条件则表明方法是签名多态方法：

  1. 在 java.lang.invoke.MethodHandle 类中声明；
  2. 只有一个 Object[] 类型的形式参数；
  3. 有一个返回值是 Object 类型的；
  4. 被设置了 ACC_VARARGS 和 ACC_NATIVE 标识。

在 Java8 中惟一的签名多态方法是 java.lang.invoke.MethodHandle 中的 invoke 和 invokeExact 方法。

为了实现句柄的调用，JVM 在 invokevirtual 指令中对签名多态方法进行的处理。方法句柄是强类型的，可直接调用该句柄所引用的底层方法，构造函数，字段，或者类似的底层操作，并且可以转换参数和返回值。这些转换非常通用的，包含转换、插入、删除和替换等模式。更多的方法可以通过 Java SE API 中的 java.lang.invoke 包查看。

异常

异常由 JVM 中的 Throwable 或者它的子类的实例表示。抛出异常实质上控制权转换，在抛出异常后，程序的控制权会从发生异常的地方转换到处理异常的地方。控制权的转换是即时的和非局部的。

大多数异常都是与发生异常的线程同步发生的；即异常都是由于当前线程的某个操作出现问题导致异常的；这种异常是同步异常。异步异常则相反，它会发生在程序运行的任何时候。

JVM 抛出异常，一般会有以下三种原因：

  • 执行了 athrow 指令；
  • JVM 同步检测到程序发生了非正常的执行情况。这些异常不会在程序中的任意位置抛出，而只会在执行以下几个指令中的某一个时就会抛出异常：
    • 有的程序执行操作引发异常的发生：
      • 指令发出了违反 Java 语言语义的操作，例如，使用超出数组大小的索引操作数组；
      • 在程序加载或者链接的时候发生错误。
    • 使用某些资源时会有资源限制，比如使用了太多的内存。
  • 异步异常出现的原因：
    • Thread 或者 ThreadGroup 执行了 stop 方法；
    • JVM 的实现内部发生了错误。

一个线程调用 stop 方法会影响另外的一个线程或者指定线程组的所有线程。这是一个异常操作，它会发生在线程运行的任何位置。另外，JVM 内部错误也会被认为是异步异常。

JVM 允许在抛出异步异常之前执行有限制的少量操作，使得代码优化器能够检测到这些异常并在可以处理异常的地方抛出。代码优化器必须在符合 Java 语义的情况下执行。

简单的 JVM 实现，可以在每个控制传输指令时，轮询异步异常。由于程序的大小都是有限的，这为检测异步异常的总延迟提供了一个界限。如果控制权转换期间不会发生异步异常，那么代码生成器就可以灵活的进行指令重排优化来获取更高的性能。(本文是Marc Feeley，Proc。1993年函数式程序设计和计算机体系结构的论文，丹麦哥本哈根，179-187页，建议作为进一步阅读。)

JVM 抛出异常的操作有非常精确的定义：当异常抛出，控制权发生改变时，在引发异常的时间点之前执行的指令都要生效；在引发异常的之后，所有的指令都不应该有什么效果。如果经过优化的代码在异常点之后执行了某些指令，那么必须把这些代码产生的影响对用户隐藏。

JVM 的每个方法都会跟零或多个异常处理处理器(exception handler)。异常处理器通过字节码偏移量，明确的它在方法代码中的有效范围；它能处理的异常类型以及处理异常的代码的位置。判断异常处理器与异常是否匹配，需要判断异常指令是否在异常处理器的偏移量范围之内，也需要判断异常是否异常处理器声明的异常，或者是其声明异常的子类型。当抛出异常时，JVM 会搜索当前方法中的异常处理器，如果找到符合的异常处理器，异常处理器会将控制权转移到处理异常的系统分支代码。
如果在当前方法中，没有找到符合的异常处理器，当前的方法会异常结束。在这种情况下，当前方法的操作数栈和局部变量表将会被丢弃，当前方法的栈帧也会出栈，并且恢复到该方法的调用者的栈帧中。然后异常会在调用者的栈帧中重新抛出，并且在方法的调用链中不断的重复前面的处理流程。如果已经到达调用链的顶端，依然没有找到符合的异常处理器来处理异常，那么引发异常的线程就会被终止。

方法异常处理器的搜索顺序非常重要。在类文件中，每个方法的异常处理器都存储在一个表中。在运行时，如果有异常抛出，JVM 会从这个表中，从上到下，搜索相应的异常处理器。

需要注意的是，JVM 不强制要求方法表中的异常处理器排序，也不强制嵌套异常方发表。Java 语言对异常语义的处理，只能通过与编译器配合才能完成。当通过其他方式生成类文件时，定义的搜索过程将确保所有Java虚拟机实现都表现一致。