相同的树

🟢 Easy · 🏷️ 树、递归、DFS · LeetCode#100

📖 题目

判断两棵二叉树 p、q 是否相同——结构相同且对应节点值相等。

💡 思路

跟对称二叉树是同一种双节点递归，甚至更简单：这题比较的是"对应位置"（p.left 跟 q.left、p.right 跟 q.right），不像对称二叉树那样要交叉比较。

边界情况：两个都空 → 相同；一空一非空 → 不同；都非空 → 比较值，再递归左右子树。

💻 代码

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[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)

时间复杂度 O(min(m, n))，m、n 是两棵树的节点数——较小的树先走完就提前结束了；空间复杂度 O(min(h1, h2))，取决于较小树的高度。