Recover Swapped Nodes in BST
Maintaining data integrity in large-scale systems is paramount. Consider a scenario where a critical Binary Search Tree (BST), used for indexing or sorted data retrieval, has been corrupted due to a rare data anomaly or a faulty maintenance operation. Specifically, exactly two nodes within the tree have had their values swapped, violating the BST property. Your task is to identify these misplaced nodes and restore the BST to its correct state without altering its structural integrity.
Your primary goal is to implement a function that takes the root of a corrupted BST as input and rectifies it. You must:
Input:
root: A TreeNode | null, representing the root of the binary search tree where exactly two node values have been swapped.
Output:
void. The function should modify the input tree in-place, correcting the swapped node values. No value should be returned.
root will not be null and will have at least two nodes.TreeNode objects or their positions in the tree structure.Examples
Example 1
Input:
root = [1,3,null,null,2]
Output:
[1,2,null,null,3]
Note:
The original tree's inorder traversal would be [1, 3, 2]. The correct inorder traversal should be [1, 2, 3]. The values 3 and 2 are swapped. After correction, the tree becomes [1, 2, null, null, 3].
Example 2
Input:
root = [3,1,4,null,null,2]
Output:
[2,1,4,null,null,3]
Note:
The original tree's inorder traversal would be [1, 3, 2, 4]. The correct inorder traversal should be [1, 2, 3, 4]. The values 3 and 2 are swapped. After correction, the tree becomes [2, 1, 4, null, null, 3].
Example 3
Input:
root = [3,2,null,null,1]
Output:
[1,2,null,null,3]
Note:
The original tree's inorder traversal would be [2, 1, 3]. The correct inorder traversal should be [1, 2, 3]. The values 2 and 1 are swapped. After correction, the tree becomes [1, 2, null, null, 3].
Constraints
n is between 2 and 1000.val) are integers in the range [-2^31, 2^31 - 1].Loading editor...