SSOJ2468对称二叉树
3215+
作者:crxis 发布:2017-09-09 分类:二叉树
题目大意:任意一个结点的度都为偶数的二叉树即对称二叉树,请判断给定的二叉树是否对称。
题目描述
如果二叉树的左右子树的结构是对称的,即两颗子树皆为空,或者皆不为空,则称该二叉树是对称的。编程判断给定的二叉树是否对称。
例:如图中的二叉树T1是对称的,T2是不对称的。
二叉树用顺序结构给出,若读到#则为空,二叉树T1=ABCDE,T2=ABCD#E,如果二叉树是对称的,输出“Yes”,反之输出”No”.
输入
输出
样例输入
ABCDE
样例输出
Yes
解题思路
后序遍历,先访问左右儿子,最后访问根,这样在访问根的时候,可以知道当前子树的结点个数,也可以知道当前根结点的儿子数量。解法就是后序遍历,s记录二叉树,c记录各个结点的儿子数。访问到叶子结点时,叶子结点的儿子数位0,在访问结束前,将其儿子数记为1,这样,下次他的父亲结点就可以通过他计算儿子个数。如果某个出现奇数个儿子,那么一票否决,ans=1标记不是对称二叉树。最后根据ans的值判断是否对称二叉树。