# 99. Recover Binary Search Tree

[Link](https://leetcode.com/problems/recover-binary-search-tree/)

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

**Example 1:**

```
Input: [1,3,null,null,2]

   1
  /
 3
  \
   2

Output: [3,1,null,null,2]

   3
  /
 1
  \
   2
```

**Example 2:**

```
Input: [3,1,4,null,null,2]

  3
 / \
1   4
   /
  2

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

  2
 / \
1   4
   /
  3
```

**Follow up:**

* A solution using O(*n*) space is pretty straight forward.
* Could you devise a constant space solution?

**Solution**

首先想到inorder traversal去找出問題的點的做法\
觀察到第一個出問題的點會比下一個大  \
&#x20;           第二個出問題的點會比上一個小\
ex. 6, 2,3,4,5, 1\
其中第一個點就是6，第二個點就是1\
只要swap 6, 1就可以recover

```
class Solution {
    public void recoverTree(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode previousNode = null;
        TreeNode firstElement = null, secondElement = null;
        while(root != null || !stack.isEmpty()){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            TreeNode node = stack.pop();
            //Travlsa to get the weird the node
            if(previousNode != null && node.val < previousNode.val){
                //need swap
                if(firstElement == null){
                    firstElement = previousNode;
                    secondElement = node;
                }
                else{
                    secondElement = node;
                    break;
                }
               
            }
            previousNode = node;
            root = node.right;
        }
        //swap
        int temp = secondElement.val;
        secondElement.val = firstElement.val;
        firstElement.val = temp;
    }
}
```

T: O(N)

S: 但空間複雜度會根據stack大小應該是O(N)\
\
若希望空間複雜度可以O(1) 那要用mirrior traversal的做法，目前沒時間準備先這樣。\
\\
