P119. 树 t 是否等于树 s 的子树

#1

https://algocasts.io/episodes/M0G2Q7mz

这个视频的哈希版本中，设计的哈希函数可能会将两棵不同的树算出相同的哈希值。将哈希函数稍作修改即可，修改如下：

  private String computeHash(TreeNode t) {
    if (t == null) return "#";
    String left = computeHash(t.left);
    String right = computeHash(t.right);
    int hash = (left + t.val + right).hashCode();
    map.put(t, hash);
    return String.valueOf(hash);
  }
#2

@Hawstein 站主有试过在OJ上提交两种解法么？引入hash的实际耗时更高（五十多毫秒），纯递归的却在十几毫秒内，可能是什么原因？

OJ 上为什么时间复杂度更优的算法却运行了更长时间
#3

@archy.shawn

OJ 上的运行时间不能作为时间复杂度的参考。时间复杂度都是统计意义上的，而 OJ 上的测试用例会有各种各样可能的 bias，不同的数据特点（数据规模大小，数据分布情况） 对不同的算法各有利弊。举个简单的例子，针对小数组的排序，O(n^2) 的插入排序实际运行时间会比 O(n*log(n)) 的快排还要少。另外还有一点，某些时间复杂度更优的算法由于引入了更复杂的数据结构，会带来一些额外的时间开销，当测试数据规模太小时，更优算法所带来的时间收益有可能小于复杂数据结构所引入的时间开销，这时也可能会发现一个时间复杂度更优的算法实际却运行了更多的时间。

因此，在 OJ 上，一个时间复杂度更小的算法却运行了更长的时间，这是很常见的。不用觉得奇怪。OJ 的测试用例最主要是保证测试的全面性，确保在测试这个算法的正确性时，考虑了所有的 case。这些测试数据并不负责 benchmark 这一块。

1赞