【经典算法】LeetCode101:对称二叉树(Java/C/Python3实现含注释说明,Easy)

2024-04-03 14:36
文章标签 java 算法 对称 二叉树 实现 说明 经典 python3 注释 easy leetcode101

本文主要是介绍【经典算法】LeetCode101:对称二叉树(Java/C/Python3实现含注释说明,Easy)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

对称二叉树

  • 题目描述
  • 思路及实现
    • 方式一：递归（推荐）
      • 思路
      • 代码实现
        • Java版本
        • C语言版本
        • Python3版本
      • 复杂度分析
    • 方式二：队列（迭代）
      • 思路
      • 代码实现
        • Java版本
        • C语言版本
        • Python3版本
      • 复杂度分析
  • 总结
  • 相似题目

  • 标签：二叉树递归、对称性判断

题目描述

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

示例 1：
在这里插入图片描述

输入：root = [1,2,2,3,4,4,3] 输出：true 示例 2：
在这里插入图片描述

输入：root = [1,2,2,null,3,null,3] 输出：false

提示：

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

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

原题： LeetCode 101

思路及实现

方式一：递归（推荐）

思路

乍一看无从下手，但用递归其实很好解决。
根据题目的描述，镜像对称，就是左右两边相等，也就是左子树和右子树是相当的。
注意这句话，左子树和右子相等，也就是说要递归的比较左子树和右子树。
我们将根节点的左子树记做 left，右子树记做 right。比较 left 是否等于 right，不等的话直接返回就可以了。
如果相当，比较 left 的左节点和 right 的右节点，再比较 left 的右节点和 right 的左节点
比如看下面这两个子树(他们分别是根节点的左子树和右子树)，能观察到这么一个规律：

左子树 2 的左孩子 == 右子树 2 的右孩子
左子树 2 的右孩子 == 右子树 2 的左孩子
2 2 / \ / 3 4 4 3 / \ / \ / \ / 8 7 6 5 5 6 7 8

根据上面信息可以总结出递归函数的两个终止条件：

  1. left 和 right 不等，或者 left 和 right 都为空
  2. 递归的比较 left，left 和 right.right，递归比较
    left，right 和 right.left

代码实现

Java版本
class Solution {public boolean isSymmetric(TreeNode root) {if (root == null) {return true;  // 如果根节点为null，即空树，视为对称二叉树，返回true}return isMirror(root.left, root.right);  // 调用isMirror方法判断左子树和右子树是否对称}private boolean isMirror(TreeNode left, TreeNode right) {if (left == null && right == null) {return true;  // 如果左子树和右子树都为null，也视为对称，返回true}if (left == null || right == null) {return false;  // 如果左子树和右子树只有一个为null，视为不对称，返回false}return left.val == right.val && isMirror(left.left, right.right) && isMirror(left.right, right.left);// 如果左子树和右子树的值相等，且同时满足左子树的左子树和右子树的右子树对称，// 以及左子树的右子树和右子树的左子树对称，则视为对称，返回true；否则，返回false}
}

说明：
isSymmetric方法是该函数的入口，接收一个二叉树的根节点作为参数。首先判断根节点是否为null，如果是，即空树，视为对称二叉树，返回true。否则，调用isMirror 方法来判断左子树和右子树是否对称。

isMirror方法是递归判断左右子树是否对称的函数。首先判断左子树和右子树是否都为null，如果是，即均为空树，视为对称，返回true。然后判断左子树和右子树中只有一个为null的情况，即一个为空树一个不为空树，视为不对称，返回false。最后，判断左子树的值和右子树的值是否相等，并且同时递归判断左子树的左子树和右子树的右子树是否对称，以及递归判断左子树的右子树和右子树的左子树是否对称。只有全部满足才视为对称，返回true；否则，返回false。

C语言版本
#include <stdbool.h>/*struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;
};
*/bool isMirror(struct TreeNode *left, struct TreeNode *right);bool isSymmetric(struct TreeNode *root) {if (root == NULL) {return true;   // 如果根节点为NULL，即空树，视为对称二叉树，返回true}return isMirror(root->left, root->right);   // 调用isMirror函数判断左子树和右子树是否对称
}bool isMirror(struct TreeNode *left, struct TreeNode *right) {if (left == NULL && right == NULL) {return true;    // 如果左子树和右子树都为NULL，也视为对称，返回true}if (left == NULL || right == NULL) {return false;   // 如果左子树和右子树只有一个为NULL，视为不对称，返回false}return (left->val == right->val) && isMirror(left->left, right->right) && isMirror(left->right, right->left);// 如果左子树和右子树的值相等，并且同时满足左子树的左子树和右子树的右子树对称，// 以及左子树的右子树和右子树的左子树对称，则视为对称，返回true；否则，返回false
}
Python3版本
class Solution:def isSymmetric(self, root: TreeNode) -> bool:if root is None:return True  # 如果根节点为空，返回True，空树被认为是对称的return self.isMirror(root.left, root.right)def isMirror(self, left: TreeNode, right: TreeNode) -> bool:if left is None and right is None:return True  # 如果左子树和右子树都为空，认为是对称的if left is None or right is None:return False  # 如果左子树和右子树只有一个为空，不对称return left.val == right.val and self.isMirror(left.left, right.right) and self.isMirror(left.right, right.left)# 比较左子树的左子树和右子树的右子树，以及左子树的右子树和右子树的左子树，满足条件才认为是对称的# 假设定义了TreeNode类，包含val、left和right属性
class TreeNode:def __init__(self, val: int = 0, left: TreeNode = None, right: TreeNode = None):self.val = valself.left = leftself.right = right

说明：代码中使用了 TreeNode 类来定义树节点，包含 val、left 和 right 属性。其中 val 存储节点的值，left 和
right 存储左子树和右子树的引用。

复杂度分析

  • 时间复杂度：O(n)，其中 n 表示树的节点数。
  • 空间复杂度：O(n)，递归调用的栈空间最多为树的高度。

方式二：队列（迭代）

思路

回想下递归的实现：
当两个子树的根节点相等时，就比较:
左子树的 left 和 右子树的 right，这个比较是用递归实现的。
现在我们改用队列来实现，思路如下：
首先从队列中拿出两个节点(left 和 right)比较：
将 left 的 left 节点和 right 的 right 节点放入队列
将 left 的 right 节点和 right 的 left 节点放入队列

代码实现

Java版本
//leetcode submit region begin(Prohibit modification and deletion)
import java.util.LinkedList;class Solution {public boolean isSymmetric(TreeNode root) {if (root == null) {return false;  // 根节点为空，不算对称}if (root.left == null && root.right == null) {return true;  // 左右子树都为空，算对称}LinkedList<TreeNode> queue = new LinkedList();  // 使用队列来保存待比较的节点queue.add(root.left);queue.add(root.right);while (queue.size() > 0) {TreeNode left = queue.removeFirst();TreeNode right = queue.removeFirst();// 只要两个节点都为空，继续循环；两者有一个为空，返回falseif (left == null && right == null) {continue;}if (left == null || right == null) {return false;}// 判断两个节点的值是否相等if (left.val != right.val) {return false;}// 将左节点的左子节点和右节点的右子节点放入队列queue.add(left.left);queue.add(right.right);// 将左节点的右子节点和右节点的左子节点放入队列queue.add(left.right);queue.add(right.left);}return true;}
}
//leetcode submit region end(Prohibit modification and deletion)

说明：
这段代码使用迭代方法判断二叉树是否对称。

在 isSymmetric 方法中，首先判断根节点是否为空，如果为空，返回 false，表示不对称。然后，如果根节点的左右子树都为空，返回 true，表示对称（只有一个元素的case）。

接下来，创建一个队列 queue，并将根节点的左子节点和右子节点加入队列。然后进入循环，每次从队列中取出两个节点进行比较。在比较过程中，只要两个节点均为空，继续循环；如果只有一个节点为空，返回
false，表示不对称。然后，比较两个节点的值是否相等，如果不相等，返回 false。

将左节点的左子节点和右节点的右子节点放入队列，用于后续比较。同时，将左节点的右子节点和右节点的左子节点放入队列，也用于后续比较。

当队列为空时，表示所有节点都已比较完毕，没有发现不对称的情况，返回 true，表示对称。

这段代码使用了迭代方法，利用队列存储待比较的节点，逐层按顺序比较，避免了递归方法的额外栈空间开销。

C语言版本
// leetcode submit region begin(Prohibit modification and deletion)
#include <stdbool.h>struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;
};bool isSymmetric(struct TreeNode* root) {if (root == NULL) {return false;  // 根节点为空，不算对称}struct TreeNode* queue[10000];  // 使用队列来保存待比较的节点int front = 0, rear = 0;queue[rear++] = root->left;queue[rear++] = root->right;while (rear != front) {struct TreeNode* left = queue[front++];struct TreeNode* right = queue[front++];// 只要两个节点都为空，继续循环；两者有一个为空，返回falseif (left == NULL && right == NULL) {continue;}if (left == NULL || right == NULL) {return false;}// 判断两个节点的值是否相等if (left->val != right->val) {return false;}// 将左节点的左子节点和右节点的右子节点放入队列queue[rear++] = left->left;queue[rear++] = right->right;// 将左节点的右子节点和右节点的左子节点放入队列queue[rear++] = left->right;queue[rear++] = right->left;}return true;
}
//leetcode submit region end(Prohibit modification and deletion)

说明：
这段代码使用C语言实现了迭代方法来判断二叉树是否对称。

在 isSymmetric 函数中，首先判断根节点是否为空，如果为空，返回 false，表示不对称。

创建一个队列 queue，使用数组来保存待比较的节点。使用 front 和 rear 变量分别表示队首和队尾的索引。

将根节点的左子节点和右子节点依次加入队列 queue。

然后进入循环，每次从队列中取出两个节点进行比较。

在比较过程中，只要两个节点均为空，继续循环；如果只有一个节点为空，返回
false，表示不对称。然后，比较两个节点的值是否相等，如果不相等，返回 false。

将左节点的左子节点和右节点的右子节点放入队列，用于后续比较。同时，将左节点的右子节点和右节点的左子节点放入队列，也用于后续比较。

当队列为空时，表示所有节点都已比较完毕，没有发现不对称的情况，返回 true，表示对称。

这段代码使用了迭代方法，利用数组队列方式存储待比较的节点，逐个按序比较，避免了递归方法的额外栈空间开销。

Python3版本
class Solution:def isSymmetric(self, root: TreeNode) -> bool:if root is None:return False  # 根节点为空，不算对称queue = []queue.append(root.left)queue.append(root.right)while queue:left = queue.pop(0)right = queue.pop(0)if left is None and right is None:continue  # 只要两个节点都为空，继续循环if left is None or right is None:return False  # 两者有一个为空，返回False，不对称if left.val != right.val:return False  # 节点值不相等，不对称queue.append(left.left)  # 左节点的左子节点入队列queue.append(right.right)  # 右节点的右子节点入队列queue.append(left.right)  # 左节点的右子节点入队列queue.append(right.left)  # 右节点的左子节点入队列return True  # 队列为空，所有节点比较完毕，对称

说明：（基础说明可查看java或者c的实现）

  1. 在函数参数的类型注解中，使用了 TreeNode 类型来标注 root 参数的类型。

  2. 使用了 is 运算符来判断节点是否为 None。is 运算符比较的是对象的身份标识，用于判断对象是否是同一个对象。这里用它来判断节点是否为None。

  3. 使用了列表 queue 来实现队列的功能，通过 append() 方法将节点加入队列的尾部，通过 pop(0)
    方法来从队列的头部取出节点。Python的列表可以很方便地实现队列的功能。

复杂度分析

  • 时间复杂度：O(n)，其中 n 表示树的节点数。在最坏情况下，需要遍历树的所有节点。
  • 空间复杂度：O(n)，最坏情况下，队列中需要存储树的一层节点，所以空间复杂度与树的高度有关。在最坏情况下，树的高度为 n/2，因此空间复杂度为 O(n)。
    综合来看，这个算法的时间复杂度和空间复杂度都是 O(n)，其中 n 表示树的节点数。算法的性能随着节点数的增加而线性增长。

总结

方法优点缺点时间复杂度空间复杂度
递归法- 直观易懂
- 代码相对简洁		- 可能导致函数调用栈溢出的风险
- 需要额外的空间来存储函数调用栈		O(n)O(n)
队列法- 不会导致函数调用栈溢出的风险
- 无需递归，代码较为直观
- 灵活的节点入队和出队顺序		- 需要手动维护队列数据结构和追踪节点的层次
- 需要额外的空间来存储队列和节点的信息		O(n)O(m)

相似题目

题目描述难度
LeetCode 100判断两个二叉树是否相同Easy
LeetCode 226反转二叉树Easy
LeetCode 104计算二叉树的最大深度Easy
LeetCode 110判断二叉树是否平衡Easy
LeetCode 222统计完全二叉树的节点个数Medium
LeetCode 124计算二叉树中的最大路径和Hard
LeetCode 199返回二叉树从右侧看的节点值列表Medium
LeetCode 116填充二叉树的每个节点的下一个右侧节点指针Medium
LeetCode 112判断二叉树是否存在从根节点到叶子节点的路径和等于给定目标值Easy
LeetCode 257返回二叉树所有从根节点到叶子节点的路径Easy

这篇关于【经典算法】LeetCode101:对称二叉树(Java/C/Python3实现含注释说明,Easy)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/873182。

相关文章

C++使用栈实现括号匹配的代码详解

C++使用栈实现括号匹配的代码详解

《C++使用栈实现括号匹配的代码详解》在编程中,括号匹配是一个常见问题,尤其是在处理数学表达式、编译器解析等任务时,栈是一种非常适合处理此类问题的数据结构,能够精确地管理括号的匹配问题,本文将通过C+... 目录引言问题描述代码讲解代码解析栈的状态表示测试总结引言在编程中，括号匹配是一个常见问题，尤其是在
阅读更多...
Java实现检查多个时间段是否有重合

Java实现检查多个时间段是否有重合

《Java实现检查多个时间段是否有重合》这篇文章主要为大家详细介绍了如何使用Java实现检查多个时间段是否有重合,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录流程概述步骤详解China编程步骤1：定义时间段类步骤2：添加时间段步骤3：检查时间段是否有重合步骤4：输出结果示例代码结语作
阅读更多...
Java中String字符串使用避坑指南

Java中String字符串使用避坑指南

《Java中String字符串使用避坑指南》Java中的String字符串是我们日常编程中用得最多的类之一,看似简单的String使用,却隐藏着不少“坑”,如果不注意,可能会导致性能问题、意外的错误容... 目录8个避坑点如下：1. 字符串的不可变性：每次修改都创建新对象2. 使用 == 比较字符串，陷阱满
阅读更多...
Java判断多个时间段是否重合的方法小结

Java判断多个时间段是否重合的方法小结

《Java判断多个时间段是否重合的方法小结》这篇文章主要为大家详细介绍了Java中判断多个时间段是否重合的方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录判断多个时间段是否有间隔判断时间段集合是否与某时间段重合判断多个时间段是否有间隔实体类内容public class D
阅读更多...
使用C++实现链表元素的反转

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定
阅读更多...
IDEA编译报错“java: 常量字符串过长”的原因及解决方法

IDEA编译报错“java: 常量字符串过长”的原因及解决方法

《IDEA编译报错“java:常量字符串过长”的原因及解决方法》今天在开发过程中,由于尝试将一个文件的Base64字符串设置为常量,结果导致IDEA编译的时候出现了如下报错java:常量字符串过长,... 目录一、问题描述二、问题原因2.1 理论角度2.2 源码角度三、解决方案解决方案①：StringBui
阅读更多...
Java覆盖第三方jar包中的某一个类的实现方法

Java覆盖第三方jar包中的某一个类的实现方法

《Java覆盖第三方jar包中的某一个类的实现方法》在我们日常的开发中,经常需要使用第三方的jar包,有时候我们会发现第三方的jar包中的某一个类有问题,或者我们需要定制化修改其中的逻辑,那么应该如何... 目录一、需求描述二、示例描述三、操作步骤四、验证结果五、实现原理一、需求描述需求描述如下：需要在
阅读更多...
Java中ArrayList和LinkedList有什么区别举例详解

Java中ArrayList和LinkedList有什么区别举例详解

《Java中ArrayList和LinkedList有什么区别举例详解》：本文主要介绍Java中ArrayList和LinkedList区别的相关资料,包括数据结构特性、核心操作性能、内存与GC影... 目录一、底层数据结构二、核心操作性能对比三、内存与 GC 影响四、扩容机制五、线程安全与并发方案六、工程
阅读更多...
JavaScript中的reduce方法执行过程、使用场景及进阶用法

JavaScript中的reduce方法执行过程、使用场景及进阶用法

《JavaScript中的reduce方法执行过程、使用场景及进阶用法》：本文主要介绍JavaScript中的reduce方法执行过程、使用场景及进阶用法的相关资料,reduce是JavaScri... 目录1. 什么是reduce2. reduce语法2.1 语法2.2 参数说明3. reduce执行过程
阅读更多...
如何使用Java实现请求deepseek

如何使用Java实现请求deepseek

《如何使用Java实现请求deepseek》这篇文章主要为大家详细介绍了如何使用Java实现请求deepseek功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1.deepseek的api创建2.Java实现请求deepseek2.1 pom文件2.2 json转化文件2.2
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2