Meta Data#
Difficulty: easy First Attempt: 2022-08-02
- Submissions: Wrong Answer → Accepted → Wrong Answer → Accepted → Wrong Answer → Accepted → Wrong Answer → Runtime Error → Accepted → Wrong Answer → Runtime Error → Wrong Answer → Accepted ×4
Approach#
Three cases (Tree Template 1):
- Both empty: equal.
- Exactly one empty: different.
- Both present: equal values and equal left and right subtrees.
My Attempts#
The failing versions all mishandled empty trees: returning nothing (None) or False for two empty trees, or True when only one was empty, e.g. [1] and [].
Solution#
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
if not p or not q:
return p is q # 兩個都是 None 才相同
return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
Complexity#
Time O(min(m, n)), space O(h).
Mistakes to Avoid#
- Two empty trees return
True; do not leave that path without a return. - One empty and one not is
False.
Interview Explanation#
I handle empty trees first: equal only if both are empty. Otherwise I compare the values and recurse on both subtrees. Time O(n).