Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Constraints
Approach
Links
Examples
Input: [1, 3, null, null, 2]
Output: [3, 1, null, null, 2]
Input: [3, 1, 4, null, null, 2]
Output: [2, 1, 4, null, null, 3]
Solutions
// Definition for a binary tree node.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
/**
* Time complexity : O(1) in the best case, and O(N) in the worst case when
* one of the swapped nodes is a rightmost leaf.
* Space complexity : up to O(H) to keep the recursion stack,
* where H is a tree height.
*/
class Solution {
private TreeNode first, last, prev;
public void recoverTree(TreeNode root) {
if(root == null) return;
findFaultyNodes(root);
if(first != null && last != null) {
int val = first.val;
first.val = last.val;
last.val = val;
}
}
// Basically inorder traversal
private void findFaultyNodes(TreeNode root) {
if(root == null) return;
findFaultyNodes(root.left);
if(prev == null) {
prev = root;
} else {
if(prev.val > root.val) {
if(first == null) {
first = prev;
}
last = root;
}
prev = root;
}
findFaultyNodes(root.right);
}
}
/**
* Time complexity : O(1) in the best case, and O(N) in the worst case when
* one of the swapped nodes is a rightmost leaf.
* Space complexity : up to O(H) to keep the recursion stack,
* where H is a tree height.
*/
class Solution {
public void recoverTree(TreeNode root) {
if(root == null) return;
TreeNode first = null, last = null, prev = null;
Deque<TreeNode> stack = new ArrayDeque();
while(!stack.isEmpty() || root != null) {
while(root != null) {
stack.add(root);
root = root.left;
}
root = stack.removeLast();
if(prev != null && prev.val > root.val) {
last = root;
if(first == null) {
first = prev;
} else {
break;
}
}
prev = root;
root = root.right;
}
if(first != null && last != null) {
int val = first.val;
first.val = last.val;
last.val = val;
}
}
}
Follow up
A solution using O(n) space is pretty straight forward.
