💬 Discord
Sign In
NeetCode #390LC-100EasyTreesBlind 75NC 150NC 250
← Back to All Problems

#390 · #100 · Same Tree(相同的树)

📌 Problem Statement & Constraints

Given the roots of two binary trees p and q, return true if they are structurally identical and every corresponding node has the same value. Constraints: the number of nodes in each tree is in [0, 100].

💡 Core Algorithmic Approaches

  1. Compare the roots recursively: both None means equal, exactly one None means unequal.
  2. If both exist, the values must match and both subtrees must match.
  3. The base cases must be checked in the order both None then either None, otherwise a None would be dereferenced.
  4. The recursion visits at most the smaller tree in full.

💻 Benchmark Python3 Implementation

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q:
            return True                    # both empty -> equal
        if not p or not q:
            return False                   # exactly one empty -> unequal
        return (p.val == q.val
                and self.isSameTree(p.left, q.left)
                and self.isSameTree(p.right, q.right))

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(min(m, n)): the recursion stops as soon as a mismatch is found.
💾 Space Complexity
O(h) for the recursion stack.

⚠️ Interview Pitfalls & Follow-ups

  • Checking p.val == q.val before the None cases: a None would raise an AttributeError.
  • Using p.val == q.val alone: the structure would not be verified, so a node with an extra child would pass.
  • Comparing only the left subtrees: both sides must be checked.
  • Assuming the trees have equal size: they may differ, which the either None case catches.