LeetCode 100: 判断两棵树是否相同（Same Tree）Java 解法详解

在 LeetCode 平台上，有一个经典的问题叫做 Same Tree，即判断两棵二叉树是否完全相同。这个问题不仅考验了程序员对树结构的理解，还测试了递归和树遍历的基本功。今天我们就来详细探讨一下这个问题的 Java 解法。

问题描述

给定两个二叉树，编写一个函数来验证它们是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例

示例 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

Java 解法

我们可以使用递归的方法来解决这个问题。递归的思想是，如果两个树的根节点相同，那么我们需要递归地比较它们的左子树和右子树。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 如果两个节点都为空，则它们是相同的
        if (p == null && q == null) return true;
        // 如果其中一个节点为空，另一个不为空，则它们不同
        if (p == null || q == null) return false;
        // 如果节点的值不同，则它们不同
        if (p.val != q.val) return false;
        // 递归地比较左子树和右子树
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

解法分析

时间复杂度: O(min(N, M))，其中 N 和 M 分别是两棵树的节点数。因为我们只需要遍历到第一个不匹配的节点或遍历完所有节点。
空间复杂度: O(min(H1, H2))，其中 H1 和 H2 是两棵树的高度。最坏情况下，树是完全不平衡的，空间复杂度为 O(min(N, M))。

应用场景

数据结构验证: 在数据结构的学习和应用中，经常需要验证两个数据结构是否相同，比如在测试二叉树的复制、镜像等操作时。
文件系统: 可以将文件系统看作一棵树，判断两个目录结构是否相同。
网络拓扑: 在网络拓扑中，判断两个网络结构是否相同。
版本控制系统: 在版本控制系统中，比较两个版本的文件树结构是否相同。
游戏开发: 在游戏中，判断两个游戏场景的树形结构是否相同。

扩展思考

非递归解法: 可以使用栈或队列来实现非递归的解法，避免递归调用的栈溢出问题。
优化: 如果树非常大，可以考虑在比较过程中提前终止，以减少不必要的比较。

通过这个 Same Tree 问题的解法，我们不仅学习了如何判断两棵树是否相同，还深入理解了递归的应用和树的遍历方法。在实际编程中，掌握这些基本技能是非常重要的。希望这篇文章能帮助大家更好地理解和解决类似的树结构问题。