Recover Binary Search Tree

Given the root of a binary search tree in which exactly two nodes were swapped by mistake, restore the tree without changing its structure. Pattern focus: Inorder Gives Sorted Sequence. A valid BST has sorted inorder traversal, so the two misplaced nodes can be identified from the violations in that sequence.

Input Format

root = binary tree root with exactly two swapped values

Output Format

corrected BST root

Constraints

  • 1 <= number of nodes <= 10^5
  • -10^9 <= node values <= 10^9
  • root must satisfy the format described in inputFormat.

Examples

Example 1:

Input:

root = [3,1,4,null,null,2]

Output:

[2,1,4,null,null,3]

Explanation:

The values 2 and 3 are swapped; restoring them gives a valid BST.

Example 2:

Input:

root = [2,3,1]

Output:

[2,1,3]

Explanation:

The left and right child values are swapped.

Loading...
Recover Binary Search Tree - Binary Search Tree