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

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

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);
    }
};

总结

这里比较外侧和内侧的节点数值,不是比较每个节点的左右孩子的值。

参考资料

 代码随想录

新学期要从学习二叉树开始! | LeetCode:101. 对称二叉树_哔哩哔哩_bilibili 


http://www.kler.cn/a/584126.html

相关文章:

  • H5端vue3 SSR 项目报错小计
  • 鸿蒙APP采用WebSocket实现在线实时聊天
  • 队列的简单例题
  • 【故障处理系列--docker卷的挂载】
  • 我又又又又又又更新了~~纯手工编写C++画图,有注释~~~
  • vs code配置 c/C++
  • 第1关:整数对
  • 鸿蒙开发者社区资源的重要性
  • K8s 1.27.1 实战系列(九)Volume
  • 【Swift】面向协议编程之HelloWorld
  • 网络安全与七层架构
  • 【AIGC图生视频】蓝耘实践:通义万相2.1进阶玩法
  • 爬虫逆向:Unicorn 详细使用指南
  • 城市客运安全员适合哪几类人报考
  • 卷积神经网络(笔记03)
  • Android调试工具之ADB
  • WPF未来展望:紧跟技术发展趋势,探索新的可能性
  • Spring Boot 集成 Lua 脚本:实现高效业务逻辑处理
  • 抖音生活服务联动监管开展专项整治 济南66家违规餐饮商家下架
  • springboot websocket语音识别翻译