<h3><a title="题目描述" href="https://leetcode-cn.com/problems/recover-binary-search-tree/">题目描述</a></h3>

<h4>方法一</h4>
<pre class="EnlighterJSRAW" data-enlighter-language="python">class Solution(object):
def recoverTree(self, root):
"""
:type root: TreeNode
:rtype: None Do not return anything, modify root in-place instead.
"""
stack = []
pre,x,y = None,None,None
while root or stack:
while root:
stack.append(root)
root = root.left
root = stack.pop()
if pre and pre.val > root.val:
y = root
if x == None:
x = pre
pre = root
root = root.right
x.val, y.val = y.val, x.val
</pre>
<p> </p>
<h4>O(1)解法:Morris 遍历算法</h4>
<pre class="EnlighterJSRAW" data-enlighter-language="python">class Solution:
def recoverTree(self, root: TreeNode) -> None:
x, y, prev = None, None, None
while root:
if root.left:
succ = root.left
while succ.right and succ.right != root:
succ = succ.right
if not succ.right:
succ.right = root
root = root.left
continue
succ.right = None
# 访问
if prev and prev.val > root.val:
if not x:
x = prev
y = root
prev = root
root = root.right
x.val, y.val = y.val, x.val
</pre>
<p> </p>
## 思路:
原地解法参考 [官方题解](https://leetcode-cn.com/problems/recover-binary-search-tree/solution/hui-fu-er-cha-sou-suo-shu-by-leetcode-solution/ "官方题解")
## 笔记&回顾:
<h4>中序遍历非递归写法</h4>
<pre class="EnlighterJSRAW" data-enlighter-language="python">
stack = []
while root or stack:
while root:
stack.append(root.left)
root = root.left
root = stack.pop()
root = root.right
</pre>
<p> </p>
<h4>Morris中序</h4>
<pre class="EnlighterJSRAW" data-enlighter-language="python">def inorder(root):
if not root: return
p = root; prenode = None
while p:
if p.left:
prenode = p.left
while prenode.right and prenode.right != p:
prenode = prenode.right
if not prenode.right: #建立链接方便回溯
prenode.right = p
p = p.left
continue
if prenode.right == p:
print(p.val) #打印
prenode.right = None #回溯完成删除多余链接
if not p.left: print(p.val) #打印
p = p.right
</pre>
<p> </p>
Leetcode99 恢复二叉搜索树