919. Recover BST — Two Swapped Nodes

Given the root of a binary search tree in which exactly two nodes' values were swapped by mistake, recover the tree by swapping those two values back (without changing its structure), and return the corrected tree as a level-order array. The tree is given as a level-order array.

Input: A level-order array of the tree.

Output: Array — the corrected BST in level order.

Examples

Input: [1,3,null,null,2]
Output: [3,1,null,null,2]
Explanation: Swap 1 and 3 to restore order.

Input: [3,1,4,null,null,2]
Output: [2,1,4,null,null,3]
Explanation: Swap 3 and 2.

Input: [2,1,3]
Output: [2,1,3]
Explanation: Already valid.

Constraints

• 2<=nodes<=10^4
• exactly two nodes swapped

Asked by