Google 面經求問

1. Given a binary tree, find if there are two subtrees that are the same. (i.e. the tree structures are the same; the values on all corresponding nodes are the same). You should find the largest subtree and don’t use brute force.




我只想到 brute-force，或是用 Map 存整個第一棵樹再掃第二顆做比較，想請問有沒有更好的想法？




2. Input a matrix, where every number is greater or equal to the numbers on its right and bottom. Output a sorted array                                         




目前我是用 merge k sorted lists 來解，也是想討論有沒有更好的解法


感謝！

第一题是不是遍历，然后用最长公共字串解.

第二题参考这题做法建heap
https://leetcode.com/problems/kt ... in-a-sorted-matrix/

第一题讲个思路吧。

假设identical的子树share一个group id. NULL的group id是0.其它子树的group id按照group在后序遍历中第一次出现的时间顺序决定。
这样我们可以一边后序遍历子树，一边建两个hashmap:
(root value, group id of left, group id of right) -> group id of root
group id -> subtrees of this group
这样我们做一遍后序遍历同时维护层数最高、subtree数量>=2的group id就行了。

这个其实跟用整棵子树的serialization作为key做法差不多，只是对key作了压缩。

第二题可不可以用小根堆来做？最右下角为小根堆的根节点，每个结点的左侧和上侧结点为该结点的左右子结点。然后不断输出并删除根节点，维护小根堆应该就可以了。
对于M*N的矩阵，树的深度为Depth ≤ M+N，每次维护的复杂度为≤O(log(Depth))，总的复杂度 <O((M*N) * log(Depth))。

merge k sorted lists的最大复杂度有可能为O(M*M*N)

hxtang 发表于 2016-7-18 02:19
第一题讲个思路吧。

假设identical的子树share一个group id. NULL的group id是0.其它子树的group id按照 ...

感謝分享！ 但有點深奧啊 ><...
請問您的 group id 是一個 len = 3 的 array 嗎？

frank11118 发表于 2016-7-18 02:51
感謝分享！ 但有點深奧啊 >

不是。group id就是一个数字，对应一棵unique的子树。
比如一棵3个结点的树，根结点是10, 两个node是20， 20.
那么group id->node的hash table存的是
0: NULL
1: leftnode, right node
2: root node

(root val, left id, right id)->root id的hashtable存的是
(20, 0, 0) : 1
(10, 1, 1) : 2

所以返回group id 1下面的两个node.

musteryu 发表于 2016-7-17 16:23
第二题可不可以用小根堆来做？最右下角为小根堆的根节点，每个结点的左侧和上侧结点为该结点的左右子结点。 ...

用heap做merge k sorted list的复杂度好像是O(log(M) MN)

hxtang 发表于 2016-7-18 03:23
不是。group id就是一个数字，对应一棵unique的子树。
比如一棵3个结点的树，根结点是10, 两个node是20 ...

了解了！
好方法，感謝分享

第一题想到一个有趣的解法，把Tree用DFS做serialization , 就变成了找substring的问题了，可以用kmp或者直接用内置方法做吧

第一题可不可以求每个节点的后续遍历然后用1个hashmap比较

jy_121 发表于 2016-7-21 15:57
第一题可不可以求每个节点的后续遍历然后用1个hashmap比较

树规模大了以后hashmap的key会越来越长。虽然hit到对应的hashkey可能还是O(1)的，但是应该还是得比较两个key是不是确实一样，这个比较是O(n)的。