পাইথনে ডিপেস্ট লিফের লোউেস্ট কমন আনসেস্টর

মনে করুন আমাদের একটি রুটেড বাইনারি ট্রি আছে, আমাদের তার ডিপেস্ট লিফগুলোর লোউেস্ট কমন আনসেস্টর (LCA) রিটার্ন করতে হবে। মনে রাখবেন:

• বাইনারি ট্রির একটি নোড লিফ নোড যদি এবং কেবল যদি সেটির কোনো চাইল্ড নেই।

• ট্রির রুটের ডেপথ ০, এবং যদি একটি নোডের ডেপথ d হয়, তবে তার চাইল্ডদের ডেপথ d+1।

• এক সেট S নোডের লোউেস্ট কমন আনসেস্টর হলো নোড A যেটির ডেপথ সবচেয়ে বড় এবং S-এর সকল নোড A-র সাবট্রি-তে থাকে।

ইনপুট যদি [1,2,3,4,5] হয়,

তবে আউটপুট হবে [2,4,5]।

এটি সমাধান করতে আমরা নিচের ধাপগুলো ফলো করব (পোস্ট-অর্ডার DFS):

• solve(node) মেথড ডিফাইন করুন:

  • যদি node না থাকে, তবে [0, None] রিটার্ন করুন।

  • যদি নোডের বাম ও ডান সাবট্রি খালি হয়, তবে [1, node] রিটার্ন করুন।

  • d1, l := solve(node.left), d2, r := solve(node.right)

  • যদি d1 > d2, তবে [d1+1, l] রিটার্ন করুন।

  • অন্যথায় যদি d2 > d1, তবে [d2+1, r] রিটার্ন করুন।

  • [d1+1, node] রিটার্ন করুন।

• মেইন মেথডে solve(root) কল করে list[1] রিটার্ন করুন।

উদাহরণ (Python)

নিচের ইমপ্লিমেন্টেশন দেখুন ভালো বুঝতে।

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

def print_tree(root):
    if root is not None:
        print_tree(root.left)
        print(root.data, end=', ')
        print_tree(root.right)

class Solution(object):
    def lcaDeepestLeaves(self, root):
        return self.solve(root)[1]

    def solve(self, node):
        if not node:
            return [0, None]
        if not node.left and not node.right:
            return [1, node]
        d1, l = self.solve(node.left)
        d2, r = self.solve(node.right)
        if d1 > d2:
            return [d1+1, l]
        elif d2 > d1:
            return [d2+1, r]
        return [d1+1, node]

ob = Solution()
root = make_tree([1,2,3,4,5])
print_tree(ob.lcaDeepestLeaves(root))

ইনপুট

[1,2,3,4,5]

আউটপুট

4, 2, 5,