NeetCode #452LC-951MediumTrees
← Back to All Problems#452 · #951 · Flip Equivalent Binary Trees(翻转等价二叉树)
📌 Problem Statement & Constraints
For a binary tree
T, a flip swaps a node's left and right children. Two trees are flip equivalent if one can be made identical to the other by a series of flips. Given two roots, return whether they are flip equivalent. Constraints: the number of nodes in each tree is in [0, 100], 0 <= Node.val <= 99.💡 Core Algorithmic Approaches
- At each node, the two subtrees may match either directly or after a flip.
- So the check is: the values match, and (
left~leftandright~right) or (left~rightandright~left). - The base cases are both
None(equivalent) and exactly oneNone(not equivalent). - This is O(min(n, m)) with early exit.
💻 Benchmark Python3 Implementation
class Solution:
def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
if not root1 and not root2:
return True # both empty
if not root1 or not root2:
return False # only one is empty
if root1.val != root2.val:
return False
# either the subtrees match directly, or after one flip
return ((self.flipEquiv(root1.left, root2.left)
and self.flipEquiv(root1.right, root2.right))
or (self.flipEquiv(root1.left, root2.right)
and self.flipEquiv(root1.right, root2.left)))⚡ Complexity Deep Dive
⏱️ Time Complexity
O(min(n, m)): the recursion stops at the first mismatch.
💾 Space Complexity
O(h) for the recursion stack.
⚠️ Interview Pitfalls & Follow-ups
- Only trying the unflipped pairing: flips are allowed at every node, so both pairings must be attempted.
- Forgetting the
exactly one Nonecase: it would dereferenceNone. - Actually mutating the trees with flips: the check is structural; no mutation is needed.
- Assuming the trees must have the same shape: flips change the shape while preserving the value multiset and the equivalence relation.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.