<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>