पायथन में बाइनरी सर्च ट्री का निम्नतम सामान्य पूर्वज

मान लीजिए हमारे पास एक बाइनरी सर्च ट्री है। हमें दो दिए गए नोड्स का निम्नतम सामान्य पूर्वज नोड ढूंढना है। दो नोड्स p और q का LCA वास्तव में ट्री में सबसे निचला नोड है जिसमें p और q दोनों वंशज के रूप में हों। यदि बाइनरी ट्री [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5] जैसा है। ट्री इस तरह होगा:

यहां 2 और 8 का LCA 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