google intern

dingshilun 发表于 2018-1-5 06:45
粗略想了想，如果要保证完全正确，可以先把这棵树所有的同构体都计算出来然后serialize，然后根据字典序 ...

这样没有意义了啊 假设有N 个节点 那么所以需要的space == O(2 ^ n)...

我昨天也面到了tree这个题，写的也是recursion的办法，面试官问能不能优化这个算法，我想了半天，他提示可以destroy这个tree，你函数的input不一定是root，然后我就说可以把input变成list of edges的形式，比如（A (B)(C))可以转化成[（A C）,(A B)]，如果tree是相似的，这个list of edges内容应该是相同的。不知道这个list of edges排序后能不能作为楼主这题的hash

wsypeter 发表于 2018-1-5 06:41
对的紫薯紫薯紫薯

按这个https://www.geeksforgeeks.org/tree-isomorphism-problem/
的说法，复杂度是O(N)呀

补充内容 (2018-1-6 05:19):
问worst case 才是n^2？

dingshilun 发表于 2018-1-5 06:45
粗略想了想，如果要保证完全正确，可以先把这棵树所有的同构体都计算出来然后serialize，然后根据字典序 ...

请问serialize是什么意思？

Honeypot666 发表于 2018-1-6 07:38
请问serialize是什么意思？

Leetcode有对应的题目，简单就是：把tree变成array

请问楼主，google的实习不是早就关了吗？怎么现在还有面试？难道是我看错了吗😢

為甚麼是recursion 是 N方阿 看了很久看不懂...z
求大神解釋

不懂怎么来的O(N^2)每个node都只走了一遍

hash function这个问题，是要让两个Similar的tree hash成同一个code？还是hash成code之后再对code再写比较的方法

jwssdwed 发表于 2018-1-6 07:48
Leetcode有对应的题目，简单就是：把tree变成array

哦哦，刷题不够，多谢解释！！！