判断（二叉）树是否镜像对称 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

判断（二叉）树是否镜像对称

判断（二叉）树是否镜像对称# JobHunting - 待字闺中

z*z2011-06-21 07:06

1 楼

二叉树的情况，左子树 inorder: node->left, node, node->right
右子树 inorder: node->right, node, node->left
这两个子树遍历相等就可以了吧
如果是N叉树的情况，正常遍历用level用queue比较简单，
判断对称有什么思路吗??

g*s2011-06-21 07:06

2 楼

it is incorrect. e.g.
0
2 1
1 2
you can KaoGu, we discussed how to check two trees are same.

【在 z**z 的大作中提到】

: 二叉树的情况，左子树 inorder: node->left, node, node->right
: 右子树 inorder: node->right, node, node->left
: 这两个子树遍历相等就可以了吧
: 如果是N叉树的情况，正常遍历用level用queue比较简单，
: 判断对称有什么思路吗??

b*82011-06-21 07:06

3 楼

In Order(先左再右边）遍历，访问左孩子则记录1，访问右孩子记录2，返回父节点记
录为0，得到一个记录串。
再来一次镜像操作：
In Order(先右边左边）遍历，访问右孩子则记录1，访问左孩子记录2，返回父节点记
录为0。
两次操作得到的记录一样，则对称。事实上，做第二次遍历时，只要时时跟第一的结果
比较，一旦发现不同马上就知道不对称，退出。此方法可简单扩展到N叉树。

g*v2011-06-21 07:06

4 楼

你的能处理2楼的情况么：
0
2 1
1 2

【在 b*******8 的大作中提到】

: In Order(先左再右边）遍历，访问左孩子则记录1，访问右孩子记录2，返回父节点记
: 录为0，得到一个记录串。
: 再来一次镜像操作：
: In Order(先右边左边）遍历，访问右孩子则记录1，访问左孩子记录2，返回父节点记
: 录为0。
: 两次操作得到的记录一样，则对称。事实上，做第二次遍历时，只要时时跟第一的结果
: 比较，一旦发现不同马上就知道不对称，退出。此方法可简单扩展到N叉树。

z*z2011-06-21 07:06

5 楼

thanks, 考前紧张脑子不转了....

i*t2011-06-21 07:06

6 楼

还是按楼主的方法,加上dummy node, 变成完全二叉树, 就可以了

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

: 你的能处理2楼的情况么：
: 0
: 2 1
: 1 2

b*82011-06-21 07:06

7 楼

这个012是什么意思？

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

: 你的能处理2楼的情况么：
: 0
: 2 1
: 1 2

a*m2011-06-21 07:06

8 楼

binary tree用递归应该可以吧。每个节点相等，左子树和右子树交叉相等就可以了。
bool mirrow(node* p1, node* p2)
{
if(!p1 && !p2) return true;
if(!p1 || !p2 )return false;
return p1->data == p2->data && mirrow(p1->left, p2->right) && mirrow(p1->
right, p2->left);
}
调用!root || mirrow(root->left,root->right);就可以了。
n叉树应该类似。