โจทย์: Binary tree มีข้อผิดพลาดที่ right child ของโหนดหนึ่งชี้ไปยังโหนดอื่นในระดับเดียวกัน (same level) ต้องหาข้อผิดพลาดนี้และลบโหนดที่ผิดรวมลูกหลาน ยกเว้นโหนดที่ถูกชี้ผิด ใช้ BFS พร้อมติดตาม parent และ visited set
อัลกอริทึม
- BFS จาก root เก็บ parent map: p[child] = (parent, is_left)
- ใช้ visited set ตรวจจับโหนดที่ถูกเยี่ยมชมซ้ำ (โหนดที่ถูกชี้ผิด)
- เมื่อเจอโหนดซ้ำ: หา grandparent และ is_left จาก parent map
- ตัด link ของ grandparent ไปยัง parent ที่ผิด (left หรือ right = None)
- คืน root ที่แก้ไขแล้ว
ตัวอย่างโค้ด
import collections
class TreeNode:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
def make_tree(elements):
Tree = TreeNode(elements[0])
for element in elements[1:]:
insert(Tree, element)
return Tree
def solve(root):
q = collections.deque([root])
p, visited = dict(), set()
while q:
cur = q.popleft()
if cur in visited:
grand_p, is_left = p[p[cur][0]]
if is_left: grand_p.left = None
else: grand_p.right = None
return root
visited.add(cur)
if cur.left:
p[cur.left] = (cur, 1)
q.append(cur.left)
if cur.right:
p[cur.right] = (cur, 0)
q.append(cur.right)
return root
# Test: create tree, add erroneous link 4->6, then fix
root = make_tree([5, 3, 7, 2, 4, 6, 8])
link_from = search_node(root, 4)
link_to = search_node(root, 6)
link_from.right = link_to
print_tree(solve(root)) # Output: 2, 3, 5, 6, 7, 8,
อินพุต/เอาต์พุต
Input: tree with erroneous link 4->6 Output (inorder): 2, 3, 5, 6, 7, 8,
โหนด 4 ถูกลบเพราะมี link ผิดไปยัง 6
