# LeetCode: 99. 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
```

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

## 解法¶

### 中序遍历找到值有误的两个节点，然后交换它们的值¶

• 因为是值交换了，所以，小值变成大值的元素的值会比它的下一个元素的值大，大值变成小值的元素的值会比它的上一个元素的值小（比如: [1, 3, 2, 4][3, 2, 1][6, 2, 3, 4, 1] ）。
• 因此，如果当前元素的值比它的下一个元素的值大的话，它就是第一个有误的节点。
• 如果当前元素的值比它的上一个元素的值小的话，它就是另一个有误的节点。

```def inorder(root):
if root is None:
return
inorder(root.left)

# print(root)

inorder(root.right)
```

```# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
def recoverTree(self, root):
self.pre = None
self.first = None
self.second = None

self.inorder(root)

self.first.val, self.second.val = self.second.val, self.first.val

return root

def inorder(self, root):
if root is None:
return

self.inorder(root.left)

if self.pre is not None and self.pre.val > root.val:
if self.first is None:
self.first = self.pre
self.second = root

self.pre = root

self.inorder(root.right)
```