【经典算法】LeetCode 100. 相同的树(Java/C/Python3/Go实现含注释说明,Easy)-阿里云开发者社区

题目描述

给定两个二叉树，编写一个函数来检验它们是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 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 <stdbool.h>
// 定义二叉树节点结构体
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 = right
class 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<TreeNode> 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 deque
class 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 main
import (
  "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<Integer> values = new HashSet<>();
        
        // 遍历第一个树，并将节点值添加到集合中
        traverse(p, values);
        
        // 检查第二个树，同时从集合中移除已检查的节点值
        return check(q, values) && values.isEmpty();
    }
    
    // 辅助方法：遍历树并将节点值添加到集合中
    private void traverse(TreeNode node, Set<Integer> values) {
        if (node == null) {
            // 当前节点为空，返回上一层
            return;
        }
        // 将当前节点值添加到集合中
        values.add(node.val);
        // 递归遍历左子树
        traverse(node.left, values);
        // 递归遍历右子树
        traverse(node.right, values);
    }
    
    // 辅助方法：检查第二个树的节点值是否都在集合中，并从集合中移除已检查的节点值
    private boolean check(TreeNode node, Set<Integer> 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 <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
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 = right
def 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 main
import (
  "fmt"
)
type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *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、大数据、数据结构算法（公众号同名），回复暗号，更能获取学习秘籍和书籍等

【经典算法】LeetCode 100. 相同的树(Java/C/Python3/Go实现含注释说明,Easy)

题目描述

思路及实现

方式一：递归

思路

代码实现

Java版本

C语言版本

Python3版本

Golang版本

复杂度分析

方式二：迭代（使用队列或栈）

思路

代码实现

Java版本

C语言版本

Python3版本

Golang版本

复杂度分析

方式三：使用集合（哈希表）

思路

代码实现（含注释）

Java版本

C语言版本

Python3版本

Golang版本

复杂度分析

总结

相似题目

热门文章

最新文章

相关课程

相关电子书

相关实验场景