代码随想录|二叉树|08对称二叉树
leetcode:101. 对称二叉树 - 力扣(LeetCode)
题目
给定一个二叉树,检查它是否是镜像对称的。
思路
二叉树是否对称,要看根节点左右的子树是否对称(以根节点为轴翻转得到),我们需要比较两个子树,在递归的过程中,同时遍历两颗子树。
我们需要比较的是两颗子树的里侧和外侧
我们定义左右两个指针p、q,p向左走,q就向右走,p向右走,q就向左走,直到p走完所有的左子树,q走完所有的右子树,保证p、q所在的节点值相等,那么这棵树就是对称的。
递归三部曲:
(1)确定递归函数的参数和返回值
我们要比较两棵树,所以参数是两棵树的节点。返回值就是布尔类型了。
bool compare(TreeNode* left, TreeNode* right)
(2)确定终止条件
我们要比较节点的数值,前提是节点不为空,否则解引用空指针,报错。
节点为空的情况有:
- 左节点为空,右节点不为空,不对称,return false
- 左不为空,右为空,不对称 return false
- 左右都为空,对称,返回true
剩下的就是节点都不为空,如果左、右节点值不同,则返回false。
(3)递归逻辑
经过了(2)的筛选之后,剩下的情况就是,左右节点不为空并且它们的值相同,我们通过以下顺序进行递归:
- 比较二叉树外侧是否对称:传入的是左节点的左孩子,右节点的右孩子。
- 比较内侧是否对称,传入左节点的右孩子,右节点的左孩子。
- 如果左右都对称就返回true ,有一侧不对称就返回false 。
三部曲之后的代码如下:
class Solution
{
public:
/**
* 比较二叉树的左子树和右子树是否对称
* @param left 左子树的根节点
* @param right 右子树的根节点
* @return 如果左子树和右子树对称,返回true;否则返回false
*/
bool compare(TreeNode *left, TreeNode *right)
{
// 如果左子树为空而右子树不为空,或者反之,则不对称
if (left == nullptr && right != nullptr)
return false;
else if (left != nullptr && right == nullptr)
return false;
// 如果左右子树都为空,则对称
else if (left == nullptr && right == nullptr)
return true;
// 如果左右子树的值不同,则不对称
else if (left->val != right->val)
return false;
// 递归比较左子树的左孩子和右子树的右孩子
bool outside = compare(left->left, right->right);
// 递归比较左子树的右孩子和右子树的左孩子
bool inside = compare(left->right, right->left);
// 返回左右子树的比较结果
return outside && inside;
}
/**
* 判断一个二叉树是否为对称二叉树
* @param root 二叉树的根节点
* @return 如果二叉树是对称的,返回true;否则返回false
*/
bool isSymmetric(TreeNode *root)
{
// 如果根节点为空,则认为是对称的
if (root == nullptr)
return true;
// 比较根节点的左子树和右子树是否对称
return compare(root->left, root->right);
}
};
总结
这里比较外侧和内侧的节点数值,不是比较每个节点的左右孩子的值。
参考资料
代码随想录
新学期要从学习二叉树开始! | LeetCode:101. 对称二叉树_哔哩哔哩_bilibili