โปรแกรมหา Lowest Common Ancestor ของโหนดหลายตัวใน Binary Tree ด้วย Python

หา LCA (Lowest Common Ancestor) ของชุดโหนดใน binary tree โดยใช้ DFS แบบ recursive: ถ้าโหนดปัจจุบันอยู่ในชุดเป้าหมาย คืนค่าโหนดนั้น ถ้าทั้งซ้ายและขวาคืนค่าไม่ใช่ None คืนค่าโหนดปัจจุบัน (เป็น LCA) มิฉะนั้นคืนค่าที่ไม่ใช่ None ระหว่างซ้าย/ขวา

ขั้นตอนการทำงาน

1. สร้างคลาส TreeNode พร้อม parent pointer
2. สร้างฟังก์ชัน search_node หาโหนดจากค่า
3. แปลงรายการค่าเป้าหมายเป็น set ของโหนด
4. DFS function fn(node) ตามตรรกะ LCA หลายโหนด
5. เรียก fn(root) ได้คำตอบ

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

import collections

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

def insert(temp, data):
    que = [temp]
    while que:
        temp = que.pop(0)
        if not temp.left:
            temp.left = TreeNode(data) if data is not None else TreeNode(0)
            break
        else:
            que.append(temp.left)
        if not temp.right:
            temp.right = TreeNode(data) if data is not None else TreeNode(0)
            break
        else:
            que.append(temp.right)

def make_tree(elements):
    Tree = TreeNode(elements[0])
    for element in elements[1:]:
        insert(Tree, element)
    return Tree

def search_node(root, element):
    if root is None: return None
    if root.data == element: return root
    res1 = search_node(root.left, element)
    if res1: return res1
    return search_node(root.right, element)

def solve(root, node_list):
    nodes = set(search_node(root, elem) for elem in node_list)
    
    def fn(node):
        if not node: return node
        if node in nodes: return node
        left, right = fn(node.left), fn(node.right)
        return node if left and right else left or right
    
    return fn(root)

root = make_tree([5, 3, 7, 2, 4, 6, 8])
print(solve(root, [6, 8]).data)  # Output: 7

อินพุต/เอาต์พุต

Input: tree [5,3,7,2,4,6,8], nodes [6,8]
Output: 7