在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
这个实现中,我们使用了一个TreeNode
类来表示BST中的节点,并定义了一些辅助函数来查找、交换和遍历BST。最后,我们定义了一个swap_nodes_in_bst
函数来找到并交换交换的节点。