C++判断二叉树是否为对称二叉树

给定一个二叉树,检查它是否是镜像对称的。 

例如,二叉树 [1,2,2,3,4,4,3] 是对称的:

但是下面这个 [1,2,3,null,3,null,3] 则不是镜像对称的:

二叉树结构: 


方法一:递归

如果一个树的左子树与右子树镜像对称,那么这个树是对称的。

递归结束条件:

1. 都为空指针则返回true

2. 只有一个为空则返回false

递归过程:

1. 判断两个指针当前节点值是否相等

2. 判断A的左子树与B的右子树是否对称

3. 判断A的右子树与B的左子树是否对称


方法二:迭代

利用队列进行迭代,队列中每两个连续的结点应该是相等的,而且它们的子树互为镜像。每次提取两个结点并比较它们的值,之后将两个结点的左右子结点按相反的顺序插入队列中,当队列为空时,或检测到树不对称(即从队列中取出两个不相等的连续结点)时结束。


最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容