পাইথনে বাইনারি ট্রির Lowest Common Ancestor (সর্বনিম্ন কমন অ্যানসেস্ট্র)

মান করুন একটি বাইনারি ট্রি আছে। আমাদের দুটি দেয়া নোডের Lowest Common Ancestor (LCA) বের করতে হবে। দুটি নোড p এবং q-র LCA হচ্ছে ট্রিতে সবচেয়ে নিচের সেই নোড যেটির নিচে p এবং q উভয়ই ডিসেন্ডেন্ট। ট্রি যদি [3,5,1,6,2,0,8,null,null,7,4] হয় তবে ট্রিটি হবে নিচের মতো:

এখানে ৫ এবং ১-এর LCA হলো ৩।

সমাধানের ধাপগুলো (রিকারসিভ পদ্ধতি):

• যদি ট্রি খালি হয়, তবে নাল রিটার্ন করুন
• যদি p এবং q উভয়ই রুটের সমান হয়, তবে রুট রিটার্ন করুন
• left := রুটের বাম সাবট্রির LCA p এবং q দিয়ে
• right := রুটের ডান সাবট্রির LCA p এবং q দিয়ে
• যদি left এবং right উভয়ই নন-জিরো হয়, তবে রুট রিটার্ন করুন
• left অথবা right রিটার্ন করুন

নিচে ইমপ্লিমেন্টেশন দেওয়া হলো:

উদাহরণ

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

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

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

ob1 = Solution()
tree = make_tree([3, 5, 1, 6, 2, 0, 8, None, None, 7, 4])
print(ob1.lowestCommonAncestor(tree, 5, 1).data)

ইনপুট

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

আউটপুট

3