รหัสบรรพบุรุษร่วมต่ำสุดของต้นไม้ค้นหาทวิภาคใน Python

สมมติว่าเรามีต้นไม้ค้นหาทวิภาค เราต้องหาโหนดบรรพบุรุษร่วมต่ำสุดของโหนดสองโหนดที่กำหนด LCA ของโหนด p และ q คือโหนดที่ต่ำที่สุดในต้นไม้ที่มีทั้ง p และ q เป็นลูกหลาน ถ้าต้นไม้แบบทวิภาคเป็น [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5] ต้นไม้จะเป็นดังนี้:

LCA ของ 2 และ 8 คือ 6

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

• ถ้าต้นไม้ว่าง ให้คืนค่า null
• ถ้า p และ q ทั้งคู่เท่ากับราก ให้คืนค่าราก
• left := LCA ของต้นไม้ย่อยซ้ายของรากโดยใช้ p และ q
• right := LCA ของต้นไม้ย่อยขวาของรากโดยใช้ p และ q
• ถ้า left และ right ทั้งคู่ไม่เป็นศูนย์ ให้คืนค่าราก
• คืนค่า left OR right

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

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

class Solution():
    def lowestCommonAncestor(self, root, p, q):
        if not root:
            return None
        if p == root or q == root:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left and right:
            return root
        return left or right

def insert(temp, data):
    que = []
    que.append(temp)
    while len(que):
        temp = que[0]
        que.pop(0)
        if not temp.left:
            temp.left = TreeNode(data)
            break
        else:
            que.append(temp.left)
        if not temp.right:
            temp.right = TreeNode(data)
            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 == None:
        return None
    if root.data == element:
        return root
    res1 = search_node(root.left, element)
    if res1:
        return res1
    res2 = search_node(root.right, element)
    return res2

root = make_tree([6,2,8,0,4,7,9,None,None,3,5])
ob1 = Solution()
op = ob1.lowestCommonAncestor(root, search_node(root, 2), search_node(root, 8))
print(op.data)

อินพุต

[6,2,8,0,4,7,9,null,null,3,5] 2 8

เอาต์พุต

6