在BST中,两个节点被随机交换,我们需要找到这两个节点并将它们交换回去

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def find_node(root, val):
    if not root:
        return None
    if root.val == val:
        return root
    left = find_node(root.left, val)
    if left:
        return left
    return find_node(root.right, val)

def swap_nodes(node1, node2):
    node1.val, node2.val = node2.val, node1.val

def traverse_bst(root):
    nodes = {}
    stack = [(root, None)]
    while stack:
        node, parent = stack.pop()
        if node:
            nodes[node.val] = parent
            stack.append((node.left, node))
            stack.append((node.right, node))
    return nodes

def find_swapped_nodes(root):
    nodes = traverse_bst(root)
    for val, parent_val in nodes.items():
        if val not in nodes:
            node1 = find_node(root, val)
            node2 = find_node(root, nodes[parent_val])
            return node1, node2

def swap_nodes_in_bst(root):
    node1, node2 = find_swapped_nodes(root)
    swap_nodes(node1, node2)
    return node1, node2