isSubTree那题经典follow up想考察什么？

最近看面经，发现binary tree那道判断isSubTree常常有个follow up:
what if one tree is significantly larger than the other one?

这个我该如何考虑呢？

请问一下这个题的原型是lintcode上那道Subtree吗？没看到有说是BST啊？

水逼一枚 发表于 2015-7-26 13:26
请问一下这个题的原型是lintcode上那道Subtree吗？没看到有说是BST啊？

笔误，已修改

会编程的猪先生 发表于 2015-7-26 13:57
笔误，已修改

好的，所以这个follow up你怎么看呢？这个题我记得我做的时候就是递归中还嵌套着递归，实际上会有很多重复运算，但是我觉得这些重复运算又没法省去。所以是不是还是在时间上有很大影响呢？

这里有O(n)的解法,不知道是不是题目想要的答案: http://www.geeksforgeeks.org/che ... -binary-tree-set-2/

handsomecool 发表于 2015-7-26 14:32
这里有O(n)的解法,不知道是不是题目想要的答案: http://www.geeksforgeeks.org/check-binary-tree-subtree- ...

没错，昨天我闭门想了一个多钟头，就是搞出这个算法。原来geek上面还真有。
不过昨天我一直没想出证明这算法正确性的依据，总觉得可能会有反例。

思路就是求出两个遍历序列（前中或者中后），然后用模式匹配算法判断包含关系，这样就可以做到线性复杂度了。

水逼一枚 发表于 2015-7-26 13:26
请问一下这个题的原型是lintcode上那道Subtree吗？没看到有说是BST啊？

这题可以有线性的算法，看我那题的解法3，昨天刚想出来的。这题被定义为简单题其实不合理。

谢谢大家啦，其实我默认为strStr这个思路就是第一问可以回答的。我本来还在想follow up是否有别的深意？或许是我想多了