# # 【LeetCode】99. Recover Binary Search Tree 解题报告（Python）

## # 题目描述：

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

Recover the tree without changing its structure.

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

## # 解题方法

``````[1, 2, 3, 4, 5, 6]  ==>  [1, 5, 3, 4, 2, 6]
``````

``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def recoverTree(self, root):
"""
:type root: TreeNode
:rtype: void Do not return anything, modify root in-place instead.
"""
self.pre, self.first, self.second = None, None, None
self.inOrder(root)
self.first.val, self.second.val = self.second.val, self.first.val

def inOrder(self, root):
if not root: return
self.inOrder(root.left)
if self.pre and self.pre.val > root.val:
if not self.first:
self.first = self.pre
self.second = root
self.pre = root
self.inOrder(root.right)
``````

## # 日期

2018 年 3 月 23 日 ———— 科目一考了100分哈哈哈哈～嗝～