行业知识
【经典算法】LeetCode 100. 相同的树(Java/C/Python3/Go实现含注释说明,Easy)
2026-10-26 00:04:43
来源：互联网转载
-
作者主页： 进朱者赤的博客
（） -
精选专栏：经典算法
-
作者简介：阿里非典型程序员一枚 ，记录在大厂的打怪升级之路。 一起学习Java、大数据、数据结构算法（公众号同名）
（） -
❤️觉得文章还不错的话欢迎大家点赞➕收藏⭐️➕评论，支持博主，记得点个大大的关注，持续更新
————————————————-
目录
- 题目描述
- 思路及实现
- 方式一：递归
- 思路
- 代码实现
- Java版本
- C语言版本
- Python3版本
- Golang版本
- 复杂度分析
- 方式二：迭代（使用队列或栈）
- 思路
- 代码实现
- Java版本
- C语言版本
- Python3版本
- Golang版本
- 复杂度分析
- 方式三：使用集合（哈希表）
- 思路
- 代码实现（含注释）
- Java版本
- C语言版本
- Python3版本
- Golang版本
- 复杂度分析
- 总结
- 相似题目
- 标签(题目类型)：树、递归、深度优先搜索
题目描述
给定两个二叉树，编写一个函数来检验它们是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。示例 1:输入: 1 1 / \ / \ 2 3 2 3 [1,2,3], [1,2,3]输出: true示例 2:输入: 1 1 / \ 2 2 [1,2], [1,null,2]输出: false示例 3:输入: 1 1 / \ / \ 2 1 1 2 [1,2,1], [1,1,2]输出: false
原题：LeetCode 100. 相同的树
思路及实现
方式一：递归
思路
递归地比较两棵树的每个节点。如果两个节点都为空，则认为它们是相同的；如果只有一个节点为空，则认为它们不相同；如果两个节点都不为空，则需要比较它们的值和左右子树是否相同。
代码实现
Java版本
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */public class Solution { public boolean isSameTree(TreeNode p, TreeNode q) { // 如果两个节点都为空，则它们是相同的 if (p == null && q == null) { return true; } // 如果只有一个节点为空，则它们不相同 if (p == null || q == null) { return false; } // 如果两个节点都不为空，则比较它们的值和左右子树是否相同 return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right); }}说明：
使用递归的思想，当两棵树都为空时返回true，当其中一个树为空而另一个不为空时返回false，否则递归比较它们的值和左右子树是否相同。
C语言版本
#include // 定义二叉树节点结构体struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right;};bool isSameTree(struct TreeNode* p, struct TreeNode* q) { // 如果两个节点都为空，则它们是相同的 if (p == NULL && q == NULL) { return true; } // 如果只有一个节点为空，则它们不相同 if (p == NULL || q == NULL) { return false; } // 如果两个节点都不为空，则比较它们的值和左右子树是否相同 return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);}说明：
C语言版本和Java版本的核心思路是一致的，只是语法有所不同。
Python3版本
# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def isSameTree(self, p: TreeNode, q: TreeNode) -> bool: # 如果两个节点都为空，则它们是相同的 if not p and not q: return True # 如果只有一个节点为空，则它们不相同 if not p or not q: return False # 如果两个节点都不为空，则比较它们的值和左右子树是否相同 return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
说明：
Python3版本的代码结构和Java、C语言版本类似，使用了Python的递归调用。
Golang版本
package main```go// Definition for a binary tree node.type TreeNode struct { Val int Left *TreeNode Right *TreeNode}func isSameTree(p *TreeNode, q *TreeNode) bool { // 如果两个节点都为空，则它们是相同的 if p == nil && q == nil { return true } // 如果只有一个节点为空，则它们不相同 if p == nil || q == nil { return false } // 如果两个节点都不为空，则比较它们的值和左右子树是否相同 return p.Val == q.Val && isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)}func main() { // 示例使用 // ...}说明：
Golang版本的代码结构和之前版本类似，只是语法和类型定义有所不同。
复杂度分析
- 时间复杂度：O(n)，其中n是两棵树中节点的总数。这是因为每个节点都会被访问一次。
- 空间复杂度：O(h)，其中h是两棵树的高度。递归调用栈的深度最坏情况下等于树的高度。在平衡树中，空间复杂度为O(log n)；在最坏情况下（退化为链表），空间复杂度为O(n)。
方式二：迭代（使用队列或栈）
思路
迭代地比较两棵树的节点，使用队列或栈来辅助遍历。具体地，可以将两棵树的根节点入队或入栈，然后在循环中依次出队或出栈，比较当前节点的值，并将它们的左右子节点依次入队或入栈。如果任何时刻两个节点的值不相等，或者一个节点有子节点而另一个没有，则返回false。
代码实现
Java版本
import java.util.LinkedList;import java.util.Queue;public class Solution { public boolean isSameTree(TreeNode p, TreeNode q) { if (p == null && q == null) { return true; } if (p == null || q == null) { return false; } Queue queue = new LinkedList(); queue.offer(p); queue.offer(q); while (!queue.isEmpty()) { TreeNode node1 = queue.poll(); TreeNode node2 = queue.poll(); if (node1 == null && node2 == null) { continue; } if (node1 == null || node2 == null || node1.val != node2.val) { return false; } queue.offer(node1.left); queue.offer(node2.left); queue.offer(node1.right); queue.offer(node2.right); } return true; }}C语言版本
C语言实现迭代遍历树通常比递归实现复杂，因为需要手动维护栈或者使用循环和指针操作来模拟队列。由于C语言没有内置队列或栈，因此这里不展示C语言的迭代实现。
Python3版本
from collections import dequeclass Solution: def isSameTree(self, p: TreeNode, q: TreeNode) -> bool: if not p and not q: return True if not p or not q: return False queue = deque([(p, q)]) while queue: node1, node2 = queue.popleft() if not node1 and not node2: continue if not node1 or not node2 or node1.val != node2.val: return False queue.append((node1.left, node2.left)) queue.append((node1.right, node2.right)) return True
Golang版本
package mainimport ("container/list")func isSameTree(p *TreeNode, q *TreeNode) bool {if p == nil && q == nil {return true}if p == nil || q == nil {return false}queue := list.New()queue.PushBack(p)queue.PushBack(q)for queue.Len() > 0 {node1 := queue.Remove(queue.Front()).(*TreeNode)node2 :=queue.Remove(queue.Front()).(*TreeNode)if node1 == nil && node2 == nil {continue}if node1 == nil || node2 == nil || node1.Val != node2.Val {return false}queue.PushBack(node1.Left)queue.PushBack(node2.Left)queue.PushBack(node1.Right)queue.PushBack(node2.Right)}return true}func main() {// 示例使用// ...}复杂度分析
- 时间复杂度：O(n)，其中n是两棵树中节点的总数。因为每个节点只会被访问一次。
- 空间复杂度：O(n)，在最坏的情况下，如果两棵树都是完全二叉树，那么需要存储所有节点，因此空间复杂度为O(n)。如果使用平衡树，空间复杂度可以降低到O(log n)。但在平均情况下，空间复杂度仍然是O(n)。
总结：递归和迭代的方法都可以用来判断两棵树是否相同。递归方法简洁直观，但可能会因为栈空间限制而导致问题。迭代方法则通过显式维护一个队列或栈来遍历树，避免了递归调用栈的问题，但代码实现相对复杂一些。在实际应用中，可以根据具体情况选择合适的方法。
方式三：使用集合（哈希表）
思路
使用集合（通常是哈希表）来存储其中一个树的节点值。然后遍历另一个树，检查每个节点的值是否都存在于集合中。如果存在，则从集合中移除该值；如果不存在，则返回false。最后，检查集合是否为空，如果为空则说明两个树是相同的，否则不同。
这种方法假设树中不包含重复值，因为集合不存储重复元素。如果树中允许重复值，那么这种方法就不适用，需要使用其他方法，比如使用计数器或更复杂的数据结构。
代码实现（含注释）
Java版本
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int val) { this.val = val; }}public class Solution { // 递归方式比较两棵树是否相同 public boolean isSameTree(TreeNode p, TreeNode q) { // 如果两个节点都为空，则它们是相同的 if (p == null && q == null) { return true; } // 如果只有一个节点为空，或者节点值不相等，则它们不是相同的 if (p == null || q == null || p.val != q.val) { return false; } // 递归检查左子树和右子树是否相同 return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); } // 使用集合的方式比较两棵树是否相同 public boolean isSameTreeHashSet(TreeNode p, TreeNode q) { // 如果两个节点都为空，则它们是相同的 if (p == null && q == null) { return true; } // 如果只有一个节点为空，或者节点值不相等，则它们不是相同的 if (p == null || q == null || p.val != q.val) { return false; } // 创建一个HashSet用于存储节点值 Set values = new HashSet(); // 遍历第一个树，并将节点值添加到集合中 traverse(p, values); // 检查第二个树，同时从集合中移除已检查的节点值 return check(q, values) && values.isEmpty(); } // 辅助方法：遍历树并将节点值添加到集合中 private void traverse(TreeNode node, Set values) { if (node == null) { // 当前节点为空，返回上一层 return; } // 将当前节点值添加到集合中 values.add(node.val); // 递归遍历左子树 traverse(node.left, values); // 递归遍历右子树 traverse(node.right, values); } // 辅助方法：检查第二个树的节点值是否都在集合中，并从集合中移除已检查的节点值 private boolean check(TreeNode node, Set values) { if (node == null) { // 当前节点为空，返回上一层 return true; } // 如果节点值不在集合中，则两棵树不相同 if (!values.contains(node.val)) { return false; } // 从集合中移除已检查的节点值 values.remove(node.val); // 递归检查左子树和右子树 return check(node.left, values) && check(node.right, values); } // 示例使用 public static void main(String[] args) { // 创建两棵树的示例 TreeNode p = new TreeNode(1); p.left = new TreeNode(2); p.right = new TreeNode(3); TreeNode q = new TreeNode(1); q.left = new TreeNode(2); q.right = new TreeNode(3); Solution solution = new Solution(); // 使用递归方式比较 boolean isSameRecursive = solution.isSameTree(p, q); System.out.println("递归方式比较结果: " + isSameRecursive); // 使用集合方式比较 boolean isSameHashSet = solution.isSameTreeHashSet(p, q); System.out.println("集合方式比较结果: " + isSameHashSet); }}代码说明：
-
isSameTree 方法是递归方式比较两棵树是否相同的实现。它首先检查两个节点是否都为空，如果都为空，则它们是相同的。然后检查是否只有一个节点为空，或者节点值是否相等，如果不满足这些条件，则它们不是相同的。最后，递归地比较左子树和右子树。
-
isSameTreeHashSet 方法是使用集合（HashSet）来比较两棵树是否相同的实现。它首先检查两个节点是否都为空，或者节点值是否相等。然后，它遍历第一个树，并将所有节点
C语言版本
#include #include #include typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right;} TreeNode;// 创建新节点TreeNode* createNode(int val) { TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode)); node->val = val; node->left = NULL; node->right = NULL; return node;}// 递归方式比较两棵树是否相同bool isSameTree(TreeNode* p, TreeNode* q) { // 如果两个节点都为空，则它们是相同的 if (p == NULL && q == NULL) { return true; } // 如果只有一个节点为空，或者节点值不相等，则它们不是相同的 if (p == NULL || q == NULL || p->val != q->val) { return false; } // 递归检查左子树和右子树是否相同 return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);}// 示例使用int main() { // 创建两棵树的示例 TreeNode* p = createNode(1); p->left = createNode(2); p->right = createNode(3); TreeNode* q = createNode(1); q->left = createNode(2); q->right = createNode(3); bool isSame = isSameTree(p, q); printf("两棵树是否相同: %s\n", isSame ? "是" : "否"); // 释放内存 // ... (需要编写相应的释放内存的代码) return 0;}代码说明
对于C语言版本，我们定义了一个TreeNode结构体，并使用malloc为节点分配内存。isSameTree函数通过递归的方式比较两棵树是否相同。需要注意的是，在实际使用中，我们还需要编写额外的代码来释放分配给树节点的内存。
Python3版本
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightdef isSameTree(p: TreeNode, q: TreeNode) -> bool: # 如果两个节点都为空，则它们是相同的 if not p and not q: return True # 如果只有一个节点为空，或者节点值不相等，则它们不是相同的 if not p or not q or p.val != q.val: return False # 递归检查左子树和右子树是否相同 return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)# 使用集合的方式def isSameTreeHashSet(p: TreeNode, q: TreeNode) -> bool: # 如果两个节点都为空，则它们是相同的 if not p and not q: return True # 如果只有一个节点为空，则它们不是相同的 if not p or not q: return False # 如果节点值不相等，则它们不是相同的 if p.val != q.val: return False # 使用集合存储第一个树的节点值 values = set() # 辅助函数，用于遍历树并添加节点值到集合中 def traverse(node): if not node: return values.add(node.val) traverse(node.left) traverse(node.right) # 遍历第一个树，并将节点值添加到集合中 traverse(p) # 遍历第二个树，检查每个节点值是否都在集合中 def check(node): if not node: return True # 如果节点值不在集合中，返回False if node.val not in values: return False # 从集合中移除已检查的节点值 values.remove(node.val) # 递归检查左子树和右子树 return check(node.left) and check(node.right) # 检查第二个树 return check(q) and not values # 确保集合为空，即第二个树中的所有节点值都被检查过
Golang版本
package mainimport ("fmt")type TreeNode struct {Val intLeft *TreeNodeRight *TreeNode}// 递归方式比较两棵树是否相同func isSameTree(p *TreeNode, q *TreeNode) bool {// 如果两个节点都为nil，则它们是相同的if p == nil && q == nil {return true}// 如果只有一个节点为nil，或者节点值不相等，则它们不是相同的if p == nil || q == nil || p.Val != q.Val {return false}// 递归检查左子树和右子树是否相同return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)}// 示例使用func main() {// 创建两棵树的示例p := &TreeNode{Val: 1}p.Left = &TreeNode{Val: 2}p.Right = &TreeNode{Val: 3}q := &TreeNode{Val: 1}q.Left = &TreeNode{Val: 2}q.Right = &TreeNode{Val: 3}isSame := isSameTree(p, q)fmt.Printf("两棵树是否相同: %t\n", isSame)}代码说明
对于Golang版本，我们同样定义了一个TreeNode结构体，但是不需要手动管理内存，因为Golang有垃圾回收机制。isSameTree函数的实现与C语言版本类似，也是通过递归的方式比较两棵树是否相同。在main函数中，我们创建了两棵树的示例，并调用isSameTree函数进行比较。
复杂度分析
-
时间复杂度：O(n)
在使用集合法解决二叉树相关问题时，时间复杂度主要由两部分组成：遍历树的时间复杂度和操作集合的时间复杂度。
遍历树的时间复杂度通常是O(n)，其中n是树中节点的数量。这是因为需要访问树中的每一个节点。
操作集合（如添加元素、检查元素是否存在）的时间复杂度通常是O(1)，这是因为HashSet等集合类型在内部使用了哈希表，使得插入和查找操作的平均时间复杂度为常数。
因此，总的时间复杂度是O(n + m)，其中m是树中不同值的数量。然而，在实际应用中，由于m通常远小于n（除非树中大部分节点的值都是重复的），所以时间复杂度可以近似看作是O(n)。
-
空间复杂度：O(m)
使用集合法的空间复杂度主要由集合本身的大小决定。在最坏情况下，如果树中每个节点的值都是唯一的，那么集合将存储所有的节点值，空间复杂度为O(m)，其中m是树中不同值的数量。如果树中有很多重复的节点值，那么集合的大小会相应减小。
需要注意的是，除了集合本身占用的空间外，还需要考虑遍历树时可能使用的其他数据结构（如栈或队列）所占用的空间。然而，在只考虑集合本身的情况下，空间复杂度是O(m)。
综上所述，使用集合法在解决二叉树相关问题时，时间复杂度通常可以看作是O(n)，而空间复杂度为O(m)，其中m是树中不同值的数量。这种方法在节点值重复较少时可能会占用较大的空间，但在某些特定场景下（如查找重复值或交集）可以非常高效。
总结
方式 优点 缺点 时间复杂度 空间复杂度 递归法 逻辑清晰，易于理解 可能导致栈溢出，空间占用随树深度增加而增加 O(n) O(h) (h为树的高度) 迭代法 不受栈大小限制，更稳定 代码相对复杂，需要维护额外的数据结构（如栈或队列） O(n) O(n) (最坏情况下) 使用集合法 时间效率高，易于实现 空间占用可能较大，尤其是当树节点值重复时 O(n) O(m) (m为树中不同值的数量) 相似题目
相似题目 难度 链接 leetcode 100. 相同的树 简单 力扣：力扣-100 ,leetcode ：leetcode-100 leetcode 144. 二叉树的前序遍历 中等 力扣：力扣-144 ,leetcode ：leetcode-144 leetcode 95. 不同的二叉搜索树 II 中等 力扣：力扣-95 ,leetcode ：leetcode-95 leetcode 94. 二叉树的中序遍历 中等 力扣：力扣-94 ,leetcode ：leetcode-94 leetcode 226. 翻转二叉树 简单 力扣：力扣-226 ,leetcode ：leetcode-226 这些题目涵盖了二叉树的不同遍历方式和结构比较，有助于加深对二叉树相关概念的理解和应用。
欢迎一键三连(关注+点赞+收藏)，技术的路上一起加油！！！代码改变世界
-
关于我：阿里非典型程序员一枚 ，记录在大厂的打怪升级之路。 一起学习Java、大数据、数据结构算法（公众号同名），回复暗号，更能获取学习秘籍和书籍等
-
—⬇️欢迎关注下面的公众号：进朱者赤，认识不一样的技术人。⬇️—
-
-
-
- 标签(题目类型)：树、递归、深度优先搜索
