前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode-101. 对称二叉树(java)

LeetCode-101. 对称二叉树(java)

作者头像
bug菌
发布2023-05-27 15:20:11
1860
发布2023-05-27 15:20:11
举报

一、前言:

👨‍🎓作者:bug菌 ✏️博客:CSDN​、掘金等 💌公众号:​​猿圈奇妙屋​​ 🚫特别声明:原创不易,转载请附上原文出处链接和本文声明,谢谢配合。 🙏版权声明:文章里可能部分文字或者图片来源于互联网或者百度百科,如有侵权请联系bug菌处理。

二、题目描述:

题目:

给你一个二叉树的根节点  ​​root​​ , 检查它是否轴对称。

具体请看如下示例:

示例 1:

LeetCode-101. 对称二叉树(java)_结点
LeetCode-101. 对称二叉树(java)_结点
代码语言:javascript
复制
输入:root = [1,2,2,3,4,4,3]
 输出:true

示例 2:

LeetCode-101. 对称二叉树(java)_结点_02
LeetCode-101. 对称二叉树(java)_结点_02
代码语言:javascript
复制
输入:root = [1,2,2,null,3,null,3]
 输出:false

提示:

  • 树中节点数目在范围 ​​[1, 1000]​​ 内
  • ​-100 <= Node.val <= 100​

题目来源: ​​LeetCode官网​​题目难度:⭐⭐

三、思路分析:

分析题意描述可得:判断树左右是否对称?其实就理解成树的镜像是否对称,也就等价于左子树是否镜像于右子树?如果同时满足下面的条件,两个树即互为镜像:

  • 它们的两个根结点具有相同的值。
  • 每个树的右子树都与另一个树的左子树镜像对称。

这还不好做么,xdm,提示到这里了都。

思路1:递归法

最让人容易想到的就是递归,递归比较左子树和右子树。具体做法:

  • 标记根节点的左子为 ​​left​​​,右子树为 ​​right​​​。比较 ​​left​​​ 是否等于 ​​right​​,不等的话直接返回就可以了。
  • 如果相当,比较 left 的左节点和 right 的右节点,再比较 left 的右节点和 right 的左节点 
  • 注意递归结束条件:left 和 right 不相等,或者 left 和 right 都为空。

思路2:迭代法

「思路一」中我们用递归的方法实现了对称性的判断。那么如何用迭代的方法实现呢?具体思路做法如下:

  1. 首先我们引入一个队列。
  2. 初始化时把根节点入队两次。
  3. 每次提取两个结点并比较它们的值(队列中每两个连续的结点应该是相等的,而且它们的子树互为镜像),然后将两个结点的左右子结点按相反的顺序插入队列中。
  4. 当队列为空时,或者检测到树不对称(即从队列中取出两个不相等的连续结点)时,迭代算法结束。 

四、算法实现:

1、递归法_AC代码

具体算法代码实现如下:

代码语言:javascript
复制
class Solution {
     public boolean isSymmetric(TreeNode root) {
         //进行递归调用
         return dg(root, root);
     }
     //递归函数
     public boolean dg(TreeNode p, TreeNode q) {
         //注意临界条件
         if (p == null && q == null) {
             return true;
         }
         if (p == null || q == null) {
             return false;
         }
         //比较树的左右节点。
         return p.val == q.val && dg(p.left, q.right) && dg(p.right, q.left);
     }
 }

2、​​迭代法​​_AC代码

具体算法代码实现如下:

代码语言:javascript
复制
class Solution {
     public boolean isSymmetric(TreeNode root) {
         return dd(root, root);
     }
     public boolean dd(TreeNode u, TreeNode v) {
  
         Queue<TreeNode> q = new LinkedList<TreeNode>();
         q.offer(u);
         q.offer(v);
         while (!q.isEmpty()) {
             u = q.poll();
             v = q.poll();
             if (u == null && v == null) {
                 continue;
             }
             if ((u == null || v == null) || (u.val != v.val)) {
                 return false;
             }
             q.offer(u.left);
             q.offer(v.right);
             q.offer(u.right);
             q.offer(v.left);
         }
         return true;
     }
 }

五、总结:

1、递归法之leetcode提交运行结果截图如下:

LeetCode-101. 对称二叉树(java)_结点_03
LeetCode-101. 对称二叉树(java)_结点_03

复杂度分析:

  • 时间复杂度:O(n)。遍历了整棵树。
  • 空间复杂度:O(n)。这里的空间复杂度和递归使用的栈空间有关,这里递归层数不超过n,故渐进空间复杂度为O(n)。

2、迭代法之leetcode提交运行结果截图如下:

复杂度分析:

  • 时间复杂度:O(n)。遍历了整棵树。
  • 空间复杂度:O(n)。

       此题还是很好玩的,对比之前有一道判断两棵树是否完全相同,解题思路都是通用的,那就是递归,但是很浪费性能。思路二是参考力扣官方提供的解题思路,我也在最后贴了希望大家也能参考一下不同的思路题解,别太局限一看到二叉树题就通用递归。

       再者,解题道路千万条,欢迎小伙伴们脑洞大开,如果你们有啥更好的想法或者思路,欢迎评论区告诉我哦,大家一起互相借鉴互相学习,方能成长的更快。

       好啦,以上就是本期的所有内容啦,咱们下期见咯。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2023-02-09,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、前言:
  • 二、题目描述:
  • 三、思路分析:
  • 四、算法实现:
    • 1、递归法_AC代码
      • 2、​​迭代法​​_AC代码
      • 五、总结:
        • 1、递归法之leetcode提交运行结果截图如下:
          • 2、迭代法之leetcode提交运行结果截图如下:
          领券
          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档