当前位置：首页 > article >正文

代码随想录|二叉树|08对称二叉树

article 2025/3/14 12:34:06

leetcode:101. 对称二叉树 - 力扣（LeetCode）

题目

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

101. 对称二叉树

思路

二叉树是否对称，要看根节点左右的子树是否对称（以根节点为轴翻转得到），我们需要比较两个子树，在递归的过程中，同时遍历两颗子树。

我们需要比较的是两颗子树的里侧和外侧

我们定义左右两个指针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);
    }
};