d********w
发帖数: 363 | 1 bool isSubTree(Tree* large, Tree * small);
假设就是二叉树吧，想到一个思路，把两个树按先序和中序打印出来，然后查看是否是
substr，能证明这样是对么？或者还有什么其他思路？感觉树的查找是个挺难的问题，
之前我在工作中就遇到过在一个domtree中，如何比较树的相似度，
就是比如把网页按dom解析，形成一个树，判断两个网页的duplicate，可以转化成求这
两个树的相似度，这又有2个问题，如何做树的查找，如何计算相似。不知大家有没有
做过这方面研究的
它的一个简化版本就是这题 |
g*********s
发帖数: 1782 | 2 recursion.
【在 d********w 的大作中提到】
: bool isSubTree(Tree* large, Tree * small);
: 假设就是二叉树吧，想到一个思路，把两个树按先序和中序打印出来，然后查看是否是
: substr，能证明这样是对么？或者还有什么其他思路？感觉树的查找是个挺难的问题，
: 之前我在工作中就遇到过在一个domtree中，如何比较树的相似度，
: 就是比如把网页按dom解析，形成一个树，判断两个网页的duplicate，可以转化成求这
: 两个树的相似度，这又有2个问题，如何做树的查找，如何计算相似。不知大家有没有
: 做过这方面研究的
: 它的一个简化版本就是这题
|
i**********e
发帖数: 1145 | 3 这题没那么容易。
我想了想，似乎很难用 bottom dfs 来解。
top down dfs 肯定可以，但是效率没那么好（有很多重复的扫描）
还有，有一个要弄清楚的是 subtree 的定义。。。
根据 wikipedia 里 subtree 的定义，
A subtree of a tree T is a tree consisting of a node in T and all of its
descendants in T.
不知道你想的 subtree 是一个 tree 里面任何一小部分，或是所有子节点都必须吻合
才行？
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 d********w 的大作中提到】
: bool isSubTree(Tree* large, Tree * small);
: 假设就是二叉树吧，想到一个思路，把两个树按先序和中序打印出来，然后查看是否是
: substr，能证明这样是对么？或者还有什么其他思路？感觉树的查找是个挺难的问题，
: 之前我在工作中就遇到过在一个domtree中，如何比较树的相似度，
: 就是比如把网页按dom解析，形成一个树，判断两个网页的duplicate，可以转化成求这
: 两个树的相似度，这又有2个问题，如何做树的查找，如何计算相似。不知大家有没有
: 做过这方面研究的
: 它的一个简化版本就是这题
|
h**********c
发帖数: 4120 | |
g*********s
发帖数: 1782 | 5 u make a good point. i think all nodes must be identical.
【在 i**********e 的大作中提到】
: 这题没那么容易。
: 我想了想，似乎很难用 bottom dfs 来解。
: top down dfs 肯定可以，但是效率没那么好（有很多重复的扫描）
: 还有，有一个要弄清楚的是 subtree 的定义。。。
: 根据 wikipedia 里 subtree 的定义，
: A subtree of a tree T is a tree consisting of a node in T and all of its
: descendants in T.
: 不知道你想的 subtree 是一个 tree 里面任何一小部分，或是所有子节点都必须吻合
: 才行？
: 一些常见面试题的答案与总结 -
|
i**********e
发帖数: 1145 | 6 Yes, they must all be identical,
but the question i'm asking is:
tree A)
2
/ \
1 3
tree B)
3
/
2
/ \
1 3
/
4
tree A) could or could not be a subtree of tree B) depending on the
definition of "subtree".
According to wikipedia's definition, tree A) is NOT a subtree of tree B),
because there is an extra node(4) at the bottom, even all nodes match
exactly.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 g*********s 的大作中提到】
: u make a good point. i think all nodes must be identical.
|
j*****u
发帖数: 1133 | 7 good point,如果子树的叶节点必须在原树中也是叶节点，可不可以这样:
原树和子树bottom->up算每个node的hash，这个hash function考虑到当前node的data和
location, i.e. hash(node)=f1(data),f2(hash(node.left)),f3(hash(node.right))
算hash是O(n)
然后foreach node，比较hash跟子树root的hash，也是O(n)
【在 i**********e 的大作中提到】
: Yes, they must all be identical,
: but the question i'm asking is:
: tree A)
: 2
: / \
: 1 3
: tree B)
: 3
: /
: 2
|
h**********c
发帖数: 4120 | 8 先查小树的高度，
查大树相同高度的全部节点，得若干个子树，
子树与小树hash 对比。 |
j***u
发帖数: 152 | 9 用DFS 如果小树是大树的子树 那么小树的开始和结束时间一定被包括在大树的开始和
结束时间内
T_start <= t_start <= t_end <= T_end |
