โปรแกรมหาระยะห่างระหว่างสองโหนดในต้นไม้แบนารีใน Python

ได้รับต้นไม้แบนารี (binary tree) ต้องหาระยะห่าง (จำนวนเส้นเชื่อม) ระหว่างโหนดสองตัว

ตัวอย่าง: ต้นไม้จาก [5,3,7,2,4,6,8] ระยะห่างระหว่าง 2 และ 8 คือ 4 (เส้น: 2-3, 3-5, 5-7, 7-8)

วิธีแก้ปัญหา

1. หา LCA (Lowest Common Ancestor) ของโหนดทั้งสอง
2. หาความห่างจาก LCA ไปแต่ละโหนดด้วย BFS
3. ผลรวมทั้งสองคือระยะห่าง

ตัวอย่างโค้ด

import collections

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

def findLca(root, p, q):
    if root is None: return None
    if root.data in (p,q): return root
    left = findLca(root.left, p, q)
    right = findLca(root.right, p, q)
    if left and right: return root
    return left or right

def findDist(root, data):
    queue = collections.deque([(root, 0)])
    while queue:
        current, dist = queue.popleft()
        if current.data == data:
            return dist
        if current.left: queue.append((current.left, dist+1))
        if current.right: queue.append((current.right, dist+1))

def solve(root, p, q):
    node = findLca(root, p, q)
    return findDist(node, p) + findDist(node, q)

อินพุต

root = make_tree([5,3,7,2,4,6,8]) print(solve(root, 2, 8))

เอาต์พุต

4