পাইথনে বাইনারি ট্রিতে একই বাম ও ডান সাবট্রি বিশিষ্ট সর্বোচ্চ সাবট্রি বের করা

ধরা যাক একটি বাইনারি ট্রি আছে। আমাদের একই বাম ও ডান সাবট্রি বিশিষ্ট সর্বোচ্চ সাবট্রি বের করতে হবে। পছন্দসই টাইম কমপ্লেক্সিটি O(n)।

ইনপুট ট্রি চিত্রে দেওয়া আছে, আউটপুট সাবট্রি রুট 70 এবং আকার 7।

সমাধানের ধাপসমূহ (পোস্ট-অর্ডার ট্রাভারসাল + এনকোডিং)

• solve(root, encode, maxSize, maxNode) ফাংশন:
  • যদি root is None: return 0
  • left_list, right_list = [""], [""]
  • ls = solve(root.left, left_list, maxSize, maxNode)
  • rs = solve(root.right, right_list, maxSize, maxNode)
  • size = ls + rs + 1
  • যদি left_list[0] == right_list[0]: size > maxSize[0] হলে maxSize এবং maxNode আপডেট করুন
  • encode[0] = "|" + left_list[0] + "|" + str(root.data) + "|" + right_list[0] + "|"
  • return size
• মেইন ফাংশনে maximum=[0], encode=[""], solve কল করুন।

উদাহরণ

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = self.right = None
def solve(root, encode, maxSize, maxNode):
    if root == None: return 0
    left_list = [""]; right_list = [""]
    ls = solve(root.left, left_list, maxSize, maxNode)
    rs = solve(root.right, right_list, maxSize, maxNode)
    size = ls + rs + 1
    if left_list[0] == right_list[0]:
        if size > maxSize[0]:
            maxSize[0] = size
            maxNode[0] = root
    encode[0] = encode[0] + "|" + left_list[0] + "|"
    encode[0] = encode[0] + "|" + str(root.data) + "|"
    encode[0] = encode[0] + "|" + right_list[0] + "|"
    return size
def largestSubtree(node, maxNode):
    maximum = [0]
    encode = [""]
    solve(node, encode, maximum, maxNode)
    return maximum
# ট্রি তৈরি
root = TreeNode(55)
root.left = TreeNode(15)
root.right = TreeNode(70)
root.left.left = TreeNode(10)
root.left.right = TreeNode(25)
root.right.left = TreeNode(75)
root.right.left.left = TreeNode(65)
root.right.left.right = TreeNode(80)
root.right.right = TreeNode(75)
root.right.right.left = TreeNode(65)
root.right.right.right = TreeNode(80)
maxNode = [None]
maximum = largestSubtree(root, maxNode)
print("Root of largest sub-tree", maxNode[0].data)
print("and its size is ", maximum)

ইনপুট

root = TreeNode(55)
root.left = TreeNode(15)
root.right = TreeNode(70)
root.left.left = TreeNode(10)
root.left.right = TreeNode(25)
root.right.left = TreeNode(75)
root.right.left.left = TreeNode(65)
root.right.left.right = TreeNode(80)
root.right.right = TreeNode(75)
root.right.right.left = TreeNode(65)
root.right.right.right = TreeNode(80)

আউটপুট

Root of largest sub-tree 70 and its size is [7]