ให้ BST ที่มีเพียง 2 โหนดที่สลับค่ากัน แก้ไขให้กลายเป็น BST ที่ถูกต้อง
ตัวอย่าง: ต้นไม้ที่ inorder ได้ [2, 6, 3, 8, 9] (ควรเป็น [2, 3, 6, 8, 9]) → สลับ 6 กับ 3
อัลกอริธึม Inorder Traversal
- เดิน inorder (ซ้าย-ราก-ขวา) ควรได้ค่าเพิ่มขึ้น
- หาจุดที่
node.val < prev.val: โหนดแรกคือmax_node(prev), โหนดที่สองคือmin_node(node) - สลับค่าของ
min_nodeและmax_node
การนำไปใช้
class TreeNode:
def __init__(self, data, left=None, right=None):
self.val = data
self.left = left
self.right = right
def __iter__(self):
if self.left:
for node in self.left: yield node
yield self
if self.right:
for node in self.right: yield node
class Solution:
def solve(self, root):
prev_node = min_node = max_node = None
found_one = False
for node in root:
if prev_node:
if node.val < prev_node.val:
if min_node is None or node.val < min_node.val:
min_node = node
if max_node is None or max_node.val < prev_node.val:
max_node = prev_node
if found_one:
break
else:
found_one = True
prev_node = node
min_node.val, max_node.val = max_node.val, min_node.val
return root
# ตัวอย่าง
root = TreeNode(3)
root.left = TreeNode(6)
root.right = TreeNode(8)
root.right.left = TreeNode(2)
root.right.right = TreeNode(9)
def print_tree(root):
if root:
print_tree(root.left)
print(root.val, end=', ')
print_tree(root.right)
ob = Solution()
print_tree(ob.solve(root)) # 2, 3, 6, 8, 9,
