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

简介: 【经典算法】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、大数据、数据结构算法公众号同名),回复暗号,更能获取学习秘籍和书籍等
相关文章
|
6天前
|
机器学习/深度学习 数据采集 搜索推荐
Python基于深度学习算法实现图书推荐系统项目实战
Python基于深度学习算法实现图书推荐系统项目实战
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战
|
4天前
|
搜索推荐 C++ Python
Python排序算法大PK:归并VS快速,谁才是你的效率之选?
【7月更文挑战第13天】归并排序** 使用分治法,稳定且平均时间复杂度O(n log n),适合保持元素顺序和并行处理。
13 5
|
5天前
|
存储 算法 搜索推荐
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
【7月更文挑战第12天】归并排序是高效稳定的排序算法,采用分治策略。Python 实现包括递归地分割数组及合并已排序部分。示例代码展示了如何将 `[12, 11, 13, 5, 6]` 分割并归并成有序数组 `[5, 6, 11, 12, 13]`。虽然 $O(n log n)$ 时间复杂度优秀,但需额外空间,适合大规模数据排序。对于小规模数据,可考虑其他算法。**
25 4
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现WOA智能鲸鱼优化算法优化支持向量机分类模型(SVC算法)项目实战
Python实现WOA智能鲸鱼优化算法优化支持向量机分类模型(SVC算法)项目实战
|
4天前
|
存储 算法 Python
“解锁Python高级数据结构新姿势:图的表示与遍历,让你的算法思维跃升新高度
【7月更文挑战第13天】Python中的图数据结构用于表示复杂关系,通过节点和边连接。常见的表示方法是邻接矩阵(适合稠密图)和邻接表(适合稀疏图)。图遍历包括DFS(深度优先搜索)和BFS(广度优先搜索):DFS深入探索分支,BFS逐层访问邻居。掌握这些技巧对优化算法和解决实际问题至关重要。**
10 1
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机分类模型(SVC算法)项目实战
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机分类模型(SVC算法)项目实战
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现GBDT(梯度提升树)分类模型(GradientBoostingClassifier算法)并应用网格搜索算法寻找最优参数项目实战
Python实现GBDT(梯度提升树)分类模型(GradientBoostingClassifier算法)并应用网格搜索算法寻找最优参数项目实战
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现PCA降维和KNN人脸识别模型(PCA和KNeighborsClassifier算法)项目实战
Python实现PCA降维和KNN人脸识别模型(PCA和KNeighborsClassifier算法)项目实战
|
6天前
|
算法 搜索推荐 编译器
算法高手养成记:Python快速排序的深度优化与实战案例分析
【7月更文挑战第11天】快速排序是编程基础,以O(n log n)时间复杂度和原址排序著称。其核心是“分而治之”,通过选择基准元素分割数组并递归排序两部分。优化包括:选择中位数作基准、尾递归优化、小数组用简单排序。以下是一个考虑优化的Python实现片段,展示了随机基准选择。通过实践和优化,能提升算法技能。**
10 3