541. Flip-Equal Trees
Two greenhouse managers each recorded the shelving layout of their greenhouse as a binary tree of tray IDs, with roots a and b. A swap picks one tray and exchanges its left and right child shelves; the entire sub-trees travel with them. Any number of swaps, at any trays, may be applied, including none.
Return true if some sequence of swaps applied to the layout a turns it into a layout identical to b, meaning the same shape with the same tray ID at every position. Otherwise return false. Two empty layouts are identical, and an empty layout never matches a non-empty one.
Each tree is given as a level-order list in which null marks a missing child.
Example 1
- Input:
- a = [4,1,6,null,8,3], b = [4,6,1,null,3,8]
- Output:
- true
- Explanation:
Swapping the children of the root, of node 1 and of node 6 turns the first tree into the second, so they are flip-equal.
Example 2
- Input:
- a = [4,1,6,null,8], b = [4,6,1,3]
- Output:
- false
- Explanation:
In the first tree node 6 is a leaf, but in the second tree no node with value 6 is a leaf, and no swaps can fix that, so the answer is false.
Example 3
- Input:
- a = [9,2,null,5], b = [9,null,2,5]
- Output:
- true
- Explanation:
One swap at the root moves the subtree of 2 to the other side, giving the second tree.
Constraints
0 ≤ number of nodes in each tree ≤ 100
-1000 ≤ Node.val ≤ 1000
All values inside one tree are distinct (the two trees may share values).
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(h)