二叉树题目:对称二叉树

这篇具有很好参考价值的文章主要介绍了二叉树题目:对称二叉树。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目

标题和出处

标题:对称二叉树

出处:101. 对称二叉树

难度

3 级

题目描述

要求

给你一个二叉树的根结点 root \texttt{root} root,检查它是否轴对称。

示例

示例 1:

二叉树题目:对称二叉树,数据结构和算法,# 树,树,二叉树

输入: root   =   [1,2,2,3,4,4,3] \texttt{root = [1,2,2,3,4,4,3]} root = [1,2,2,3,4,4,3]
输出: true \texttt{true} true

示例 2:

二叉树题目:对称二叉树,数据结构和算法,# 树,树,二叉树

输入: root   =   [1,2,2,null,3,null,3] \texttt{root = [1,2,2,null,3,null,3]} root = [1,2,2,null,3,null,3]
输出: false \texttt{false} false

数据范围

  • 树中结点数目在范围 [1,   1000] \texttt{[1, 1000]} [1, 1000]
  • -100 ≤ Node.val ≤ 100 \texttt{-100} \le \texttt{Node.val} \le \texttt{100} -100Node.val100

进阶

你可以运用递归和迭代两种方法解决这个问题吗?

解法一

思路和算法

如果二叉树的左子树和右子树对称,则二叉树是对称二叉树。对称二叉树的左子树和右子树的结构和结点值满足左右翻转。

深度优先搜索的做法是,首先判断根结点的左子结点和右子结点是否存在和是否符合对称二叉树的要求,如果左子结点和右子结点存在且符合对称二叉树的要求,则继续对左子树和右子树判断。

由于二叉树的结构具有递归性,因此可以使用递归实现深度优先搜索。

p p p q q q 分别表示根结点的左子结点和右子结点。如果 p p p q q q 都为空,则原始二叉树是对称二叉树。如果 p p p q q q 只有一个为空,则原始二叉树的结构不符合对称二叉树的要求,因此原始二叉树不是对称二叉树。这两种情况是递归的终止条件。

对于其余情况,首先判断 p p p q q q 的结点值是否相同,然后执行递归。

  1. 如果 p p p q q q 的结点值不同,则原始二叉树不是对称二叉树。

  2. 如果 p p p q q q 的结点值相同,则只有当 p p p 的左子树和 q q q 的右子树对称且 p p p 的右子树和 q q q 的左子树对称时,原始二叉树才是对称二叉树。对 p p p q q q 的左右子树执行递归,判断原始二叉树是否为对称二叉树。

代码

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return areSymmetric(root.left, root.right);
    }

    public boolean areSymmetric(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        return p.val == q.val && areSymmetric(p.left, q.right) && areSymmetric(p.right, q.left);
    }
}

复杂度分析

  • 时间复杂度: O ( n ) O(n) O(n),其中 n n n 是二叉树的结点数。每个结点都被访问一次。

  • 空间复杂度: O ( n ) O(n) O(n),其中 n n n 是二叉树的结点数。空间复杂度主要是递归调用的栈空间,取决于二叉树的高度,最坏情况下二叉树的高度是 O ( n ) O(n) O(n)

解法二

思路和算法

也可以使用广度优先搜索遍历二叉树,判断二叉树是否为对称二叉树。

由于需要判断二叉树的左半部分和右半部分是否对称,因此需要同时从两个相反的方向遍历二叉树。使用两个队列分别存储两个方向遍历二叉树访问的结点。初始时将两个二叉树的根结点分别入两个队列,遍历过程中,每次从两个队列分别将一个结点出队列,这两个出队列的结点一定是两个二叉树中对称位置的两个结点,这两个结点分别称为结点一和结点二,执行如下操作。

  1. 如果两个结点值不同,则两个二叉树的对称位置处的两个结点值不同,因此二叉树不是对称二叉树。

  2. 如果两个结点值相同,则分别获得两个结点的左子结点和右子结点,如果结点一的左子结点和结点二的右子结点恰好有一个为空,或者结点一的右子结点和结点二的左子结点恰好有一个为空,则二叉树的结构不符合对称二叉树的要求,因此二叉树不是对称二叉树。

  3. 如果两个结点的左子结点和右子结点的结构符合对称二叉树的要求,则将两个结点的非空子结点分别入相应的队列,如果两个结点的左子结点和右子结点都不为空,则结点一的左子结点和右子结点依次入第一个队列,结点二的右子结点和左子结点依次入第二个队列。

当队列为空时,遍历结束,如果在任意位置,二叉树的结构和结点值都符合对称二叉树的要求,则二叉树是对称二叉树。

代码

class Solution {
    public boolean isSymmetric(TreeNode root) {
        Queue<TreeNode> queue1 = new ArrayDeque<TreeNode>();
        Queue<TreeNode> queue2 = new ArrayDeque<TreeNode>();
        queue1.offer(root);
        queue2.offer(root);
        while (!queue1.isEmpty()) {
            TreeNode node1 = queue1.poll();
            TreeNode node2 = queue2.poll();
            if (node1.val != node2.val) {
                return false;
            }
            TreeNode left1 = node1.left, right1 = node1.right, left2 = node2.left, right2 = node2.right;
            if (left1 == null ^ right2 == null) {
                return false;
            }
            if (right1 == null ^ left2 == null) {
                return false;
            }
            if (left1 != null) {
                queue1.offer(left1);
                queue2.offer(right2);
            }
            if (right1 != null) {
                queue1.offer(right1);
                queue2.offer(left2);
            }
        }
        return true;
    }
}

复杂度分析

  • 时间复杂度: O ( n ) O(n) O(n),其中 n n n 是二叉树的结点数。每个结点在两个方向各访问一次。

  • 空间复杂度: O ( n ) O(n) O(n),其中 n n n 是二叉树的结点数。空间复杂度主要是队列空间,每个队列内元素个数不超过 n n n文章来源地址https://www.toymoban.com/news/detail-530546.html

到了这里,关于二叉树题目:对称二叉树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】二叉树的相关操作以及OJ题目

    当一个树不是满二叉树或完全二叉树时,它是不适合使用数组存储的,它应该使用链式结构来存储。 再看二叉树基本操作前,再回顾下二叉树的概念,二叉树是: 空树 非空:根节点,根节点的左子树、根节点的右子树组成的。 从概念中可以看出,二叉树定义是递归式的,因

    2024年03月19日
    浏览(48)
  • 二叉树题目:对称二叉树

    标题:对称二叉树 出处:101. 对称二叉树 3 级 要求 给你一个二叉树的根结点 root texttt{root} root ,检查它是否轴对称。 示例 示例 1: 输入: root   =   [1,2,2,3,4,4,3] texttt{root = [1,2,2,3,4,4,3]} root = [1,2,2,3,4,4,3] 输出: true texttt{true} true 示例 2: 输入: root   =   [1,2,2,null,3,null,

    2024年02月12日
    浏览(33)
  • C++力扣题目101--对称二叉树

    力扣题目链接(opens new window) 给定一个二叉树,检查它是否是镜像对称的。   首先想清楚,判断对称二叉树要比较的是哪两个节点,要比较的可不是左右节点! 对于二叉树是否对称,要比较的是根节点的左子树与右子树是不是相互翻转的,理解这一点就知道了 其实我们要比较

    2024年01月25日
    浏览(37)
  • 二叉树OJ题目合集(单值、对称、平衡、构建加遍历)

    目录 前言: 一:单值二叉树 二:二叉树遍历 核心点 (1)前序 (2)中序 (3)后序 三:判断两颗树是否相同 四:判断二叉树是否对称 五:判断一颗树是否为另一颗树的子树 六:平衡二叉树 七:二叉树的构建加遍历 这一部分适合已经 适用于已经掌握二叉树基础的同学(遍历,求节

    2024年02月02日
    浏览(37)
  • 【数据结构-二叉树】二叉树

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月07日
    浏览(47)
  • 数据结构:搜索二叉树 | 平衡二叉树

    博客写的代码都放在这里:gitee仓库链接 1.二叉搜索树 1.1.基本概念 二叉搜索树又称二叉排序树, 可以为空,如果不为空具有以下性质的二叉树 : 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值 若它的右子树不为空,则右子树上所有节点的值都大于根节点的

    2024年01月23日
    浏览(55)
  • 【数据结构和算法】--- 二叉树(3)--二叉树链式结构的实现(1)

    在学习二叉树的基本操作前,需先要创建一棵二叉树,然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入,且为了方便后面的介绍,此处手动快速创建一棵简单的二叉树,快速进入二叉树操作学习,等二叉树结构了解的差不多时,我们反过头再来研

    2024年01月25日
    浏览(59)
  • 【数据结构】二叉树——链式结构

    目录  一、前置声明 二、二叉树的遍历 2.1 前序、中序以及后序遍历 2.2 层序遍历 三、节点个数以及高度 3.1 节点个数 3.2 叶子节点个数 3.3 第k层节点个数 3.4 二叉树的高度/深度 3.5 查找值为x的节点 四、二叉树的创建和销毁 4.1 构建二叉树 4.2 二叉树销毁 4.3 判断二叉树

    2024年02月16日
    浏览(44)
  • 【数据结构】二叉树——顺序结构

    由于每个节点都 只有一个父节点 ,所以我们可通过双亲来表示一棵树。具体方式通过 数组的形式 实现。 根节点的下标为0 按照层序从上到下排序 每层从左向右递增 表示形式: 二维数组 数据的列标为0 ,只需确定行标,即可锁定位置 根节点的父节点下标为 -1 列标为1存父节

    2024年02月02日
    浏览(54)
  • 数据结构-二叉树-二叉树左右孩子交换(递归)

     注:本文采用队列和递归的算法进行创建和层次遍历。同时不能采用BFS和DFS,因为需要把当前根节点的左孩、右孩勾链并输入才能递归下一个根节点; 队列用于存储此时应该递归的根节点; 格式:每一行尾不能有空格; Description 根据输入利用二叉链表创建二叉树,并将所

    2024年02月04日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包