恢复二叉搜索树

描述

困难

二叉搜索树中的两个节点被错误地交换。

请在不改变其结构的情况下，恢复这棵树。

示例 1:

输入: [1,3,null,null,2]   1
  /
 3
  \
   2输出: [3,1,null,null,2]   3
  /
 1
  \
   2

示例 2:

输入: [3,1,4,null,null,2]3/ \1   4  / 2输出: [2,1,4,null,null,3]2/ \1   4  / 3

解题

一颗正常搜索树的中序遍历值时递增的

如果遍历时出现了不是递增的情况，那就是错误的节点

先找出错误的两个节点，再进行交换

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution:def __init__(self):self.first_node = None	# 错误的第一个节点self.second_node = None	# 错误的第二个节点self.last_node = TreeNode(-2**32)	# 设置上一个节点，初始设置为最小值def recoverTree(self, root: TreeNode) -> None:"""Do not return anything, modify root in-place instead."""self.find_node(root)self.first_node.val, self.second_node.val = self.second_node.val, self.first_node.valdef find_node(self, root):if not root:return if root.left:self.find_node(root.left)# 如果还没找到第一个错误的节点，且当前节点的值小于上一个节点值，说明上一个节点为错误节点if not self.first_node and self.last_node.val >= root.val:self.first_node = self.last_node# 已经找到的第一个节点，且当前节点的值小于上一个节点值，说明当前节点为错误节点if self.first_node and self.last_node.val >= root.val:self.second_node = root# 更新上一个节点self.last_node = rootif root.right:self.find_node(root.right)