【数据结构与算法】判断二叉树是否对称
【摘要】 给你一个二叉树的根节点root， 检查它是否轴对称。
判断一颗二叉树是否对称的解题思路可以通过比较两个子树是否镜像对称来实现。
具体地说，如果一棵树的左子树与右子树是镜像对称的，那么这棵树就是对称的。这个问题可以通过递归来解决。
目录
一、问题描述
给你一个二叉树的根节点
root， 检查它是否轴对称。
二、解题思路
判断一颗二叉树是否对称的解题思路可以通过比较两个子树是否镜像对称来实现。
具体地说，如果一棵树的左子树与右子树是镜像对称的，那么这棵树就是对称的。这个问题可以通过递归来解决。
解题思路如下：
- 首先，比较根节点：如果二叉树为空，那么它是对称的（空树是对称的）。如果二叉树只有一个节点（即根节点），那么它也是对称的。
- 其次，递归地比较左子树和右子树：对于非空树，我们需要递归地比较它的左子树和右子树。具体来说，我们需要先比较左子树和右子树的结构和数据是否相同，然后再交叉比较左子树的左子树和右子树的右子树，以及左子树的右子树和右子树的左子树。
- 递归终止条件：在递归过程中，如果两个节点都为空，那么它们是对称的。如果只有一个节点为空，或者两个节点的值不相等，那么它们不是对称的。
- 要注意的是解决这个问题需要两个函数实现:
- 第一个函数接收一个树的根结点，判断树是否空以及调用子函数；
- 第二个函数接收两个节点的值进行对比，这两个节点可能是左子树的根和右子树的根，也可能是左子树的右子树和右子树的左子树，或是左子树的左子树和右子树的右子树
三、C语言实现代码
struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
};
typedef struct TreeNode TNode;
bool _isSymmetric(TNode* root1, TNode* root2)//子树判断函数
{
if (root1 == NULL && root2 == NULL)
return true;
if (root1 == NULL || root2 == NULL)//结构对比
return false;
if (root1->val != root2->val)//数据对比
return false;
return _isSymmetric(root1->left, root2->right)//对左右子树的节点交叉判断
&& _isSymmetric(root1->right, root2->left);
}
bool isSymmetric(struct TreeNode* root)
{
if (root == NULL)
return true;
return _isSymmetric(root->left, root->right);//调用子函数
}
【声明】本内容来自华为云开发者社区博主，不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息，否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）