# 恢复二叉搜索树
给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。
进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？
示例 1：
输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
示例 2：
输入：root = [3,1,4,null,null,2]
输出：[2,1,4,null,null,3]
解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。
提示：
- 树上节点的数目在范围
[2, 1000] 内 -231 <= Node.val <= 231 - 1
## template
```python
import sys
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def to_list(self, count):
queue = []
queue.append(self)
result = []
while len(queue) > 0:
if count == 0:
break
node = queue.pop(0)
if node is None:
result.append('null')
else:
count -= 1
result.append(node.val)
queue.append(node.left)
queue.append(node.right)
return result
class List2Tree(object):
def __init__(self, nums: list):
self.nums = nums
self.queue = []
if len(nums) == 1:
self.root = TreeNode(self.nums.pop(0))
else:
a = self.nums.pop(0)
b = self.nums.pop(0)
c = self.nums.pop(0)
self.root = TreeNode(a)
if b is not None:
self.root.left = TreeNode(b)
else:
self.root.left = b
if c is not None:
self.root.right = TreeNode(c)
else:
self.root.right = c
self.queue.append(self.root.left)
self.queue.append(self.root.right)
def convert(self):
while len(self.nums) > 0 and len(self.queue) > 0:
node = self.queue.pop(0)
if node is not None:
num = self.nums.pop(0)
if num is not None:
node.left = TreeNode(num)
else:
node.left = num
if len(self.nums) > 0:
num = self.nums.pop(0)
else:
num = None
if num is not None:
node.right = TreeNode(num)
else:
node.right = num
self.queue.append(node.left)
self.queue.append(node.right)
return self.root
class Solution(object):
def __init__(self):
self.first = self.second = None
self.pre = TreeNode(-sys.maxsize - 1)
def recoverTree(self, root):
length = len(root)
root = List2Tree(root).convert()
self.traverse(root)
self.first.val, self.second.val = self.second.val, self.first.val
return root.to_list(length)
def traverse(self, root):
if root is None:
return
self.traverse(root.left)
if self.pre.val >= root.val:
if self.first is None:
self.first = self.pre
if self.first is not None:
self.second = root
self.pre = root
self.traverse(root.right)
# %%
s = Solution()
print(s.recoverTree(root=[1, 3, None, None, 2]))
```
## 答案
```python
```
## 选项
### A
```python
```
### B
```python
```
### C
```python
```