LeetCode算法题-Symmetric Tree（Java实现）
2024-09-04 08:34:18
这是悦乐书的第163次更新，第165篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第22题（顺位题号是101）。给定二叉树，检查它是否是自身的镜像（即，围绕其中心对称）。
例如，这个二叉树[1,2,2,3,4,4,3]是对称的：
1
/ \
2 2
/ \ / \
3 4 4 3
但是以下[1,2,2，null，3，null，3]不是：
1
/ \
2 2
\ \
3 3
本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。
02 第一种解法
如果你看过昨天的Same Tree题，看到今天这道题时，有没有什么想法？可能你已经发现了，要判断一个二叉树是否中心对称，如果把它从根节点“一分为二”的看做两个二叉树，只要判断这两个二叉树的左右节点是否对称相等即可，即左边新的二叉树的左节点值和右边新的二叉树的右节点值相等。对此，我们可以借助昨天的代码，很容易的就将其写出来。
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return isSameTree(root.left, root.right);
}
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null || q == null) {
return p == q;
}
boolean f = p.val == q.val;
boolean f2 = isSameTree(p.left, q.right);
boolean f3 = isSameTree(p.right, q.left);
return f && f2 && f3;
}
03 第二种解法
除了上面的递归方法外，我们还可以使用另外一种解法。
题目的意思是只要每个节点的值对称相等就行，那我们可以将每层节点的值存起来，然后再进行比较，直到比较完所有的值。因为是自顶向下比较，所以先存起来的值就需要先拿出来比较，我们可以使用队列来当做存值的载体，借助其先进先出的特性。
public boolean isSymmetric2(TreeNode root) {
if (root == null) {
return true;
}
Queue<TreeNode> q = new LinkedList<>();
q.add(root.left);
q.add(root.right);
while (!q.isEmpty()) {
TreeNode t1 = q.poll();
TreeNode t2 = q.poll();
if (t1 == null && t2 == null) {
continue;
}
if (t1 == null || t2 == null) {
return false;
}
if (t1.val != t2.val) {
return false;
}
q.add(t1.left);
q.add(t2.right);
q.add(t1.right);
q.add(t2.left);
}
return true;
}
04 小结
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
最新文章
- iOS开发之AFNetworking 3.0.4使用
- Swift建立栈的泛型结构体以及top()、push()、pop()定义函数的定义
- python的一些图像操作
- spi 子系统
- OBIEE 11g 启动与停止包含服务器重启
- 关于玩QQ消息导入导出功能的感想！
- 二模11day2解题报告
- JQuery获取浏览器窗口的高度和宽度
- 数往知来 ASP.NET 表单的提交_url传值_重定向 <十八>
- Redis的安装与使用
- virtalBox共享文件夹设置
- Windows下FFmpeg快速入门 <第二篇>
- [置顶] 深圳华为BSS公共部件 (BI 商业智能 Java Javascript)
- [置顶] Vector ArrayList区别剖析
- 关于map()与filter()
- Android----drawable state各个属性详解----ListView几个比较特别的属性：
- 百叶窗特效（用move.js库）
- EF 6.0
- Swift中的"可溢出"算术运算符
- 关于Tensorflow安装opencv和pygame