j****3
发帖数: 129 | 1 给一个n-ary tree，如何判断内部是否存在identical subtree？返回一个true/false
求大神指点。。G家考的面试题，可是网上查了下怎么都是可以写成paper的算法。。。
补充：网上paper的算法是找到所有identical subtree，我这个问题应该简单一些。。 |
j****3
发帖数: 129 | |
l********s
发帖数: 358 | 3 DFS and serialize the subtree to a string, insert the string in a HashSet.
If the string already exists in the HashSet, we have two identical sub-
trees. |
b******g
发帖数: 3616 | 4 这个DFS如何保证：当serialize出来的两个string一样时，一定这两个subtree也
identical呢？
【在 l********s 的大作中提到】
: DFS and serialize the subtree to a string, insert the string in a HashSet.
: If the string already exists in the HashSet, we have two identical sub-
: trees.
|
l********s
发帖数: 358 | 5 I think we can pre-order serialize n-array tree similar to binary tree using
sentinels such as '#'.
http://leetcode.com/2010/09/serializationdeserialization-of-bin
【在 b******g 的大作中提到】
: 这个DFS如何保证：当serialize出来的两个string一样时，一定这两个subtree也
: identical呢？
|
e********2
发帖数: 495 | 6 serialize之后就用prefix tree啊！
【在 b******g 的大作中提到】
: 这个DFS如何保证：当serialize出来的两个string一样时，一定这两个subtree也
: identical呢？
|
n*******e
发帖数: 37 | 7 对identical subtree的定义不是很了解
想问一下, 如果有下面这个tree:
1
/ | \
3 2 5
/
3
其中的两个3算是identical subtree吗? |
l********s
发帖数: 358 | 8 算！
【在 n*******e 的大作中提到】
: 对identical subtree的定义不是很了解
: 想问一下, 如果有下面这个tree:
: 1
: / | \
: 3 2 5
: /
: 3
: 其中的两个3算是identical subtree吗?
|
d****n
发帖数: 233 | 9 Post order traversal， 同时对每个子树算ｈａｓｈ， 遇到ｃｏｎｆｌｉｃｔ，
再深度比较。
false
【在 j****3 的大作中提到】
: 给一个n-ary tree，如何判断内部是否存在identical subtree？返回一个true/false
: 求大神指点。。G家考的面试题，可是网上查了下怎么都是可以写成paper的算法。。。
: 补充：网上paper的算法是找到所有identical subtree，我这个问题应该简单一些。。
|
