b******g
发帖数: 1721 | 1 我现在想到的就是
1. 先遍历t1 and t2, 找到他们的size，
2. 假设t2比较小，然后就是看t1有无t2
3. 那么我的算法就是
match(Tree t1, Tree t2){
if(t1.value=t2.value)
return match(t1.left,t2.left) && match(t1.right,t2.right);
else
return match(t1.left,t2) || match(t1.right,t2);
}
complexity |t2|*|t1|
有无更好的算法？ | p*****2
发帖数: 21240 | 2
code感觉不是很对呀。不过复杂度也应该就是这个了。没什么好办法。不过这个复杂度
是worst case。
【在 b******g 的大作中提到】
: 我现在想到的就是
: 1. 先遍历t1 and t2, 找到他们的size，
: 2. 假设t2比较小，然后就是看t1有无t2
: 3. 那么我的算法就是
: match(Tree t1, Tree t2){
: if(t1.value=t2.value)
: return match(t1.left,t2.left) && match(t1.right,t2.right);
: else
: return match(t1.left,t2) || match(t1.right,t2);
: }
| r*******n
发帖数: 3020 | 3 相同是指子树的结点个数相同？
【在 b******g 的大作中提到】
: 我现在想到的就是
: 1. 先遍历t1 and t2, 找到他们的size，
: 2. 假设t2比较小，然后就是看t1有无t2
: 3. 那么我的算法就是
: match(Tree t1, Tree t2){
: if(t1.value=t2.value)
: return match(t1.left,t2.left) && match(t1.right,t2.right);
: else
: return match(t1.left,t2) || match(t1.right,t2);
: }
| w**z
发帖数: 8232 | 4 What is your base step?
You need to remember the match t1 node (Let's mark it MatchRoot) the as t2'
root.
If you find the unmatch, you need to back from the previous matching root (
MatchRoot) and going down again from its children. | b******g
发帖数: 1721 | 5 相同是说不光结构相同，而且每个对应的value也相同。根据peking2 和 wwzz建议，我
给个全的，也是个大概，可能边角没有考虑。
int matchRoot(Tree t1, Tree t2)
{
Queue q1=new Queue();
q1.enqueue(t2);
int size=0;
while(q1.size()){
Tree tmp=q1.dequeue();
if(!match(t1,tmpTree)){
if(!tmp.left)
q1.enqueue(tmp.left);
if(!tmp.right)
q1.enqueue(tmp.right);
}else{
size=tmp.size();
}
}
return size;
}
match(Tree t1, Tree t2){
if(t1.value=t2.value)
return match(t1.left,t2.left) && match(t1.right,t2.right);
else
return match(t1.left,t2) || match(t1.right,t2);
} | w**z
发帖数: 8232 | 6 You don't have your base step for your recursive match method. Your method
runs in to NPE eventually
Need to check t1.left/right, t2.left/righ == null. All of null, return true.
If children structure mismatch, (t1 has left, t2 doesn't, etc) return false.
If children structure match, recursively calling match with non-null
children |
|
