弱问怎么判断两个binary tree相同？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

弱问怎么判断两个binary tree相同？

弱问怎么判断两个binary tree相同？# JobHunting - 待字闺中

c*t2012-10-14 07:10

1 楼

比较一遍in-order,再比较一遍pre-order,可以吗？

l*a2012-10-14 07:10

2 楼

为什么不是root比
然后左子树与左子树比。。。

【在 c********t 的大作中提到】

: 比较一遍in-order,再比较一遍pre-order,可以吗？

g*e2012-10-14 07:10

3 楼

怎么判断两个binary tree互为镜像？

【在 l*****a 的大作中提到】

: 为什么不是root比
: 然后左子树与左子树比。。。

n*s2012-10-14 07:10

4 楼

是binary search tree吗？

c*t2012-10-14 07:10

5 楼

对啊，我做题做糊涂了
写一个
public static boolean isSame( Node a, Node b ) {
if( a == null && b == null ) {
return true;
}else if( a != null && b != null ) {
return a.data == b.data &&
isSame( a.left, b.left ) && isSame( a.right, b.right );
}else {
return false;
}
}

【在 l*****a 的大作中提到】

: 为什么不是root比
: 然后左子树与左子树比。。。

c*t2012-10-14 07:10

6 楼

bst有区别吗？

【在 n*****s 的大作中提到】

: 是binary search tree吗？

c*t2012-10-14 07:10

7 楼

先翻转一个，在判断相不相同？
public void reverse(Node a){
if(a == null) return;
reverse(a.left);
Node tmp = a.left;
a.left = a.right;
a.right = tmp;
reverse(a.left);
}
可行吗？

【在 g**e 的大作中提到】

: 怎么判断两个binary tree互为镜像？

l*a2012-10-14 07:10

8 楼

左跟右比，右跟左比?

【在 g**e 的大作中提到】

: 怎么判断两个binary tree互为镜像？

l*a2012-10-14 07:10

9 楼

太冗余

【在 c********t 的大作中提到】

: 对啊，我做题做糊涂了
: 写一个
: public static boolean isSame( Node a, Node b ) {
: if( a == null && b == null ) {
: return true;
: }else if( a != null && b != null ) {
: return a.data == b.data &&
: isSame( a.left, b.left ) && isSame( a.right, b.right );
: }else {
: return false;

c*t2012-10-14 07:10

10 楼

好像对，唉，我又弱了
写一个
public static boolean isSame( Node a, Node b ) {
if( a == null && b == null ) {
return true;
}else if( a != null && b != null ) {
return a.data == b.data &&
isSame( a.left, b.right ) && isSame( a.right, b.left );
}else {
return false;
}
}

【在 l*****a 的大作中提到】

: 左跟右比，右跟左比?

c*t2012-10-14 07:10

11 楼

求简化

【在 l*****a 的大作中提到】

: 太冗余

n*s2012-10-14 07:10

12 楼

a a
/ \ 跟 / \ 算同一个树吗
b c c b

t*22012-10-14 07:10

13 楼

显然不

【在 n*****s 的大作中提到】

: a a
: / \ 跟 / \ 算同一个树吗
: b c c b

n*s2012-10-14 07:10

14 楼

那先BFS按照层序给所有结点标上号，然后挨个比较left child和right child行不行？

【在 t*******2 的大作中提到】

: 显然不

l*a2012-10-14 07:10

15 楼

更正一下，
不要那么多else不好吗？是不是更清晰一点

【在 c********t 的大作中提到】

: 求简化

i*y2012-10-14 07:10

16 楼

我用一个比较弱的办法，用level-order遍历，然后每个level用isEvenPalindrome判断
是不是true

【在 l*****a 的大作中提到】

: 左跟右比，右跟左比?

y*g2012-10-14 07:10

17 楼

这个不对吧
a
/
b
和
a
\
b

【在 i****y 的大作中提到】

: 我用一个比较弱的办法，用level-order遍历，然后每个level用isEvenPalindrome判断
: 是不是true

c*t2012-10-14 07:10

18 楼

明白了，这样行不？
public static boolean isSame( Node a, Node b ) {
if( a != null && b != null ) {
return a.data == b.data &&
isSame( a.left, b.left ) && isSame( a.right, b.right );
}
return a == null && b == null;
}

【在 l*****a 的大作中提到】

: 更正一下，
: 不要那么多else不好吗？是不是更清晰一点

i*y2012-10-14 07:10

19 楼

null 需要设置为#

【在 y*******g 的大作中提到】

: 这个不对吧
: a
: /
: b
: 和
: a
: \
: b