google intern

昨天Onsite面最后一轮第二题也是similar tree。我给出的时间复杂度是h*(2^h), h表示满二叉树的高度，大概也算接近n^2。但是最后几分钟follow up题是能不能优化时间复杂度，也就是不用DFS搜索。给出的答案是类似Scramble String思路，但是具体如何把树encode成合适的字符串从而用Scramble String的DP做法没有想到。最后问面试官他会怎么做，他也只是说关键是要把树encode成比较巧妙的字符串格式再比较，没有给具体答案。

用hash function计算，我的思路是计算每一node的md5 hash值, 计算方法是根据他的left child的hash，还有right child的hash，还有他自己的值计算出他这个node的hash值。recursive计算的话，只需要traversal tree一遍；比较的时候，只需要比较root的hash值就可以知道是否是similar的了。