1、题目描述：
2、题解：
方法1：中序遍历迭代
二叉搜索树的性质：
1、若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
2、若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
3、任意节点的左、右子树也分别为二叉查找树；
4、没有键值相等的节点。
思路：
二叉搜索树的中序遍历是有序的比如[4,2,3,1] 交换 4和1即可代码精髓：设置两个节点：第一个节点，是第一个按照中序遍历时前一个节点大于后一个节点，的前一个节点，即4第二个节点，是第一个节点找到后，再出现前一个节点大于后一个节点的，后一个节点，即1if not self.firstNode and self.pre.val >= root.val:self.firstNode = self.preif self.firstNode and self.pre.val >= root.val:self.secondNode = root找到这两个节点后，交换节点值即可
Python代码如下：
# Definition for a binary tree node.# class TreeNode:#def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution:def recoverTree(self, root: TreeNode) -> None:"""Do not return anything, modify root in-place instead."""#中序遍历迭代firstNode = NonesecondNode = Nonepre = TreeNode(float('-inf'))stack = []p = rootwhile p or stack:while p:stack.append(p)p = p.leftp = stack.pop()if not firstNode and pre.val > p.val:firstNode = preif firstNode and pre.val > p.val:secondNode = ppre = pp = p.rightfirstNode.val,secondNode.val = secondNode.val,firstNode.val
方法2：中序遍历递归
思路：
二叉搜索树的中序遍历是有序的比如[4,2,3,1] 交换 4和1即可代码精髓：设置两个节点：第一个节点，是第一个按照中序遍历时前一个节点大于后一个节点，的前一个节点，即4第二个节点，是第一个节点找到后，再出现前一个节点大于后一个节点的，后一个节点，即1找到这两个节点，交换值即可
Python代码如下：
# Definition for a binary tree node.# class TreeNode:#def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution:def recoverTree(self, root: TreeNode) -> None:"""Do not return anything, modify root in-place instead."""# 中序遍历递归self.firstNode ,self.secondNode = None,Noneself.pre = TreeNode(float('-inf'))def in_order(root):if not root:returnin_order(root.left)if not self.firstNode and self.pre.val >= root.val:self.firstNode = self.preif self.firstNode and self.pre.val >= root.val:self.secondNode = rootself.pre = rootin_order(root.right)in_order(root)self.firstNode.val,self.secondNode.val = self.secondNode.val,self.firstNode.val
方法3：Morris中序遍历
可以参考力扣94题
面试算法：二叉树的Morris遍历算法
# Definition for a binary tree node.# class TreeNode:#def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution:def recoverTree(self, root: TreeNode) -> None:"""Do not return anything, modify root in-place instead."""# Morris中序遍历firstNode,secondNode = None,Nonepre = TreeNode(float('-inf'))cur = rootwhile cur:if not cur.left:if not firstNode and pre.val >= cur.val:firstNode = preif firstNode and pre.val >= cur.val:secondNode = curpre = curcur = cur.rightelse:#找左子树的最右边的节点temp = cur.leftwhile temp.right and temp.right != cur:temp = temp.rightif not temp.right:temp.right = curcur = cur.leftif temp.right == cur:temp.right = Noneif not firstNode and pre.val >= cur.val:firstNode = preif firstNode and pre.val >= cur.val:secondNode = curpre = curcur = cur.rightfirstNode.val ,secondNode.val = secondNode.val,firstNode.val
3、复杂度分析：
方法1：
时间复杂度：O(N),N为结点的个数
空间复杂度：O(H)，H为二叉树的深度
方法2：
时间复杂度：O(N),N为结点的个数
空间复杂度：O(H)，H为二叉树的深度
方法3:
时间复杂度：O(N)
空间复杂度：O(1)
如果觉得《深度优先搜索DFS | Morris遍历:力扣99. 恢复二叉搜索树》对你有帮助，请点赞、收藏，并留下你的观点哦！
