题目
- 给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。
法一、中序遍历
class Solution:
def recoverTree(self, root: TreeNode) -> None:
"""
Do not return anything, modify root in-place instead.
"""
firstNode = None #用于记录需要交换的节点
secondNode = None
pre = TreeNode(float("-inf")) #辅助变量，记录遍历过程中的前一个节点
stack = []#创建一个栈，用于遍历二叉树
p = root #p 作为当前遍历的节点
while p or stack: #当 p 不为空或栈不为空时，进行循环。
while p:#将节点 p 及其左子节点依次入栈，直到左子节点为空。
stack.append(p)
p = p.left
p = stack.pop() #出栈一个节点 p，并进行以下判断
if not firstNode and pre.val > p.val:#如果 firstNode 为空且 pre.val > p.val，
firstNode = pre
if firstNode and pre.val > p.val:#如果 firstNode 不为空且 pre.val > p.val，则说明第一个错误节点已记录，并且当前节点 p 与其前一个节点 pre 顺序颠倒，即找到了第二个错误节点。将其赋值给 secondNode。
secondNode = p
pre = p#更新 pre 为当前节点 p，用于下一次比较
p = p.right#将 p 更新为其右子节点，继续下一轮循环
firstNode.val, secondNode.val = secondNode.val, firstNode.val#交换两个错误的节点
#由于函数要求修改原始树的节点值，而不是返回新的树，因此直接交换了节点的值，而没有返回任何内容。
法二、中序遍历+排序
class Solution:
def recoverTree(self, root: TreeNode) -> None:
# 中序遍历函数，将节点按中序遍历顺序添加到列表中
def inorder_traversal(node):
if not node:
return []
return inorder_traversal(node.left) + [node] + inorder_traversal(node.right)
# 中序遍历二叉搜索树，得到节点列表
nodes = inorder_traversal(root)
# 对节点列表按节点值进行排序
sorted_nodes = sorted(nodes, key=lambda x: x.val)
# 找到需要交换的两个错误节点
p, q = None, None
for i in range(len(nodes)):
if nodes[i] != sorted_nodes[i]:
if not p:#如果 p 还没有赋值
p = nodes[i]
else:
q = nodes[i]
break
# 交换 p 和 q 的值
p.val, q.val = q.val, p.val
class Solution:
def recoverTree(self, root: TreeNode) -> None:
#定义了一个匿名函数 Trees，该函数用于进行中序遍历。它通过递归地遍历左子树、根节点和右子树，并将节点依次添加到一个列表中。
Trees = lambda x: [] if not x else Trees(x.left) + [x] + Trees(x.right)
#得到了二叉搜索树中所有节点的列表 a，其中节点的顺序是中序遍历的顺序。
a = Trees(root)
sa = sorted(a, key=lambda x: x.val)#对列表排序
p, q = [a[i] for i in range(len(a)) if a[i] != sa[i]]#通过遍历列表 a，找到在两个列表中不同的节点，分别赋值给 p 和 q。
p.val, q.val = q.val, p.val#交换 p 和 q 的值