当前位置:首页 > 数据结构 > 二叉树 > 正文
SSOJ2468对称二叉树
779+

题目大意:任意一个结点的度都为偶数的二叉树即对称二叉树,请判断给定的二叉树是否对称。

题目描述

如果二叉树的左右子树的结构是对称的,即两颗子树皆为空,或者皆不为空,则称该二叉树是对称的。编程判断给定的二叉树是否对称。

例:如图中的二叉树T1是对称的,T2是不对称的。

二叉树用顺序结构给出,若读到#则为空,二叉树T1=ABCDE,T2=ABCD#E,如果二叉树是对称的,输出“Yes”,反之输出”No”.

输入

输出

样例输入

ABCDE

样例输出

Yes

解题思路

后序遍历,先访问左右儿子,最后访问根,这样在访问根的时候,可以知道当前子树的结点个数,也可以知道当前根结点的儿子数量。解法就是后序遍历,s记录二叉树,c记录各个结点的儿子数。访问到叶子结点时,叶子结点的儿子数位0,在访问结束前,将其儿子数记为1,这样,下次他的父亲结点就可以通过他计算儿子个数。如果某个出现奇数个儿子,那么一票否决,ans=1标记不是对称二叉树。最后根据ans的值判断是否对称二叉树。

程序实现

更多

About

坚决不Copy代码!

本文标签:,,,

SSOJ2468对称二叉树:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter