100. 相同的树 - Same Tree

🎯 问题描述（来源于LeetCode）

描述：
给定两个二叉树的根节点 p 和 q，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

说明：

两棵树均由 TreeNode 节点组成，每个节点包含整数值 val 以及指向左子节点 left 和右子节点 right 的指针。
空树用 None 表示。

示例：

示例 1：

1 2	输入: p = [1,2,3], q = [1,2,3] 输出: true

示例 2：

1 2	输入: p = [1,2], q = [1,null,2] 输出: false

💻 解题思路

思路1：递归深度优先比较（DFS）

算法步骤

处理空节点情况：
- 如果 p 或 q 有一个是 None（空节点），则只有当两者同时为 None 时才算相同，否则不同。
- 等价于：若其中一个为 None，则返回 p == q（即 p is None and q is None）。
比较当前节点值：
- 如果当前两个节点都不为空，则先比较它们的 val 是否相等。
递归比较子树：
- 当节点值相等时，继续递归比较左子树（p.left, q.left）和右子树（p.right, q.right）。
- 只有左右子树都相同，整棵树才相同。
返回结果：
- 最终返回 (val 相等) && 左子树相同 && 右子树相同。

思路1：代码实现

# 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: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if p is None or q is None:
            return q == p
        return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

思路1：📊 性能分析

复杂度验证

时间复杂度： $O(\min(n, m))$ ，其中 $n$ 、 $m$ 分别是两棵树的节点数。最坏情况下需要遍历所有节点（当两棵树相同时）。
空间复杂度： $O(\min(h_1, h_2))$ ，其中 $h_1$ 、 $h_2$ 是树的高度。递归调用栈的深度取决于较矮树的高度，最坏情况（链状树）为 $O(\min(n, m))$ 。