Tổ tiên chung thấp nhất của cây tìm kiếm nhị phân trong Python

Cho cây tìm kiếm nhị phân, tìm tổ tiên chung thấp nhất (LCA) của hai nút p, q. LCA là nút thấp nhất có cả p và q là hậu duệ. Ví dụ cây [6,2,8,0,4,7,9,null,null,3,5], LCA của 2 và 8 là 6.

Giải pháp

Đệ quy:

• Nếu cây rỗng → null.
• Nếu p hoặc q là gốc → trả về gốc.
• left = LCA(cây con trái), right = LCA(cây con phải).
• Nếu left và right đều khác null → trả về gốc.
• Trả về left hoặc right.

Ví dụ

Triển khai Python:

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)

Đầu vào

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

Đầu ra

6