โปรแกรมหา LCA ของ Binary Tree ใช้ Parent Pointer ด้วย Python

เมื่อ TreeNode มี parent pointer หา LCA ของ 2 โหนดได้ง่ายโดย: สร้าง path จากโหนดแรกขึ้นไป root เก็บใน list แล้วเดินจากโหนดที่สองขึ้นไป root ตรวจสอบว่าอยู่ใน path แรกหรือไม่ โหนดแรกที่เจอคือ LCA

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

1. สร้าง path_p_r list จากโหนด x ขึ้นไป root ผ่าน parent
2. เดินจากโหนด y ขึ้นไป root ตรวจสอบ if y in path_p_r: return y
3. ซ้ำจนกว่าจะเจอหรือถึง root

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

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

def insert(temp, data):
    que = [temp]
    while que:
        temp = que.pop(0)
        if not temp.left:
            temp.left = TreeNode(data, parent=temp) if data is not None else TreeNode(0, parent=temp)
            break
        else:
            que.append(temp.left)
        if not temp.right:
            temp.right = TreeNode(data, parent=temp) if data is not None else TreeNode(0, parent=temp)
            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(x, y):
    path_p_r = []
    while x:
        path_p_r.append(x)
        x = x.parent
    while y:
        if y in path_p_r:
            return y
        y = y.parent

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

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

Input: tree, nodes 3 and 7
Output: 5