# Recover Binary Search Tree

ID: 691; medium; 恢复二叉搜索树

## Solution 1 (Java)

``````/**
* Definition of TreeNode:
* public class TreeNode {
*     public int val;
*     public TreeNode left, right;
*     public TreeNode(int val) {
*         this.val = val;
*         this.left = this.right = null;
*     }
* }
*/

public class Solution {
/**
* @param root: the given tree
* @return: the tree after swapping
*/
public TreeNode bstSwappedNode(TreeNode root) {
// nodes inorder should be non-decreasing
List<TreeNode> nodes = new ArrayList<>();
inorderTraversal(root, nodes);

TreeNode firstWrongNode = null, secondWrongNode = null;
for (int i = 1; i < nodes.size(); i++) {
if (nodes.get(i).val < nodes.get(i - 1).val) {
if (firstWrongNode == null)
firstWrongNode = nodes.get(i - 1);
secondWrongNode = nodes.get(i);
}
}

if (firstWrongNode != null) {
int temp = firstWrongNode.val;
firstWrongNode.val = secondWrongNode.val;
secondWrongNode.val = temp;
}

return root;
}

private void inorderTraversal(TreeNode root, List<TreeNode> nodes) {
if (root == null)
return;
inorderTraversal(root.left, nodes);
inorderTraversal(root.right, nodes);
}
}``````

### Notes

• Use inorder traversal and put the nodes into a list.

• The list should be in non-decreasing order by construction. Iterate the list to find the node that is smaller than its previous node, then swap these two nodes.

• Space complexity is `O(n)`

## Solution 2 (Java)

``````/**
* Definition of TreeNode:
* public class TreeNode {
*     public int val;
*     public TreeNode left, right;
*     public TreeNode(int val) {
*         this.val = val;
*         this.left = this.right = null;
*     }
* }
*/

public class Solution {

TreeNode first = null, second = null, prev = null;

/**
* @param root: the given tree
* @return: the tree after swapping
*/
public TreeNode bstSwappedNode(TreeNode root) {
prev = new TreeNode(Integer.MIN_VALUE);
inorderTraversal(root);

if (first != null) {
int temp = first.val;
first.val = second.val;
second.val = temp;
}
return root;
}

private void inorderTraversal(TreeNode root) {
if (root == null)
return;

inorderTraversal(root.left);
if (root.val < prev.val) {
if (first == null)
first = prev;
second = root;
}
prev = root;
inorderTraversal(root.right);
}
}``````

### Notes

• We still use inorder traversal but modify it to check if we have any out-of-order nodes (the two nodes that are not in non-decreasing order).

• Space complexity is `O(1)`

Last updated