567. Flip Equivalent Binary Trees
A flip at a node of a binary tree swaps that node's left and right subtrees. Two binary trees are flip equivalent if one can be turned into the other by performing any number of flips, at any nodes.
Given the roots of two binary trees, root1 and root2, return true if the trees are flip equivalent and false otherwise.
Within each tree every node value is unique.
Example 1:
Input: root1 = [1,2,3,4,5], root2 = [1,3,2,null,null,5,4]
Output: true
Explanation: Flip at node 1 (swapping the subtrees rooted at 2 and 3), then flip at node 2 (swapping leaves 4 and 5). The first tree becomes exactly the second.
Example 2:
Input: root1 = [1,2,3,4], root2 = [1,3,2,4]
Output: false
Explanation: In the first tree the leaf 4 hangs under node 2, but in the second it hangs under node 3. Flips move whole subtrees around a parent — they can never move 4 to a different parent, so no sequence of flips works.
Constraints:
- Each tree has between 0 and 100 nodes.
- 0 ≤ node value ≤ 99
- Values are unique within each tree.
Hints:
Compare the trees top-down. If the two roots differ in value (or exactly one is missing), no flip anywhere below can fix that — flips never change a node's own value.
When the roots match, their children must pair up one of two ways: left-with-left and right-with-right (no flip at this node), or left-with-right and right-with-left (one flip). Recurse on both pairings.
Because values are unique, at most one of the two pairings can survive past the child value check — so the recursion stays linear instead of exploding.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root1 = [1,2,3,4,5], root2 = [1,3,2,null,null,5,4]
Expected output: true