পাইথনে বাইনারি ট্রির লংগেস্ট কনsekutিভ পথের দৈর্ঘ্য বের করার প্রোগ্রাম

ধরি আমাদের একটি বাইনারি ট্রি আছে; আমাদের বাইনারি ট্রির লংগেস্ট পথ বের করতে হবে।

তাই, ইনপুট যদি নিচের ট্রি হয়, তবে আউটপুট হবে ৫ কারণ লংগেস্ট কনsekutিভ সিকোয়েন্স হলো [2, 3, 4, 5, 6]।

সমাধানের ধাপগুলো:

• যদি root নাল হয়, তবে
  • ০ রিটার্ন করুন
• maxPath := 0
• helper() ফাংশন ডিফাইন করুন। এটি node নিবে
  • inc := 1, dec := 1
  • যদি node.left নাল না হয়, তবে
    • [left_inc, left_dec] := helper(node.left)
  • অন্যথায়, [0, 0]
  • যদি node.right নাল না হয়, তবে
    • [right_inc, right_dec] := helper(node.right)
  • অন্যথায়, [0, 0]
  • যদি লেফট চাইল্ড আছে এবং node.val - node.left.val == 1, তবে
    • inc := max(inc, left_inc + 1)
  • অন্যথায় যদি লেফট চাইল্ড আছে এবং node.val - node.left.val == -1, তবে
    • dec := max(dec, left_dec + 1)
  • যদি রাইট চাইল্ড আছে এবং node.val - node.right.val == 1, তবে
    • inc := max(inc, right_inc + 1)
  • অন্যথায় যদি রাইট চাইল্ড আছে এবং node.val - node.right.val == -1, তবে
    • dec := max(dec, right_dec + 1)
  • যদি দুটি চাইল্ড থাকে এবং left.val - node.val == 1 এবং node.val - right.val == 1, তবে
    • maxPath := max(maxPath, left_dec + right_inc + 1)
  • অন্যথায় যদি দুটি চাইল্ড থাকে এবং left.val - node.val == -1 এবং node.val - right.val == -1, তবে
    • maxPath := max(maxPath, left_inc + right_dec + 1)
  • maxPath := max(maxPath, inc, dec)
  • inc, dec রিটার্ন করুন
• মেইন মেথড থেকে করুন
  • helper(root)
  • maxPath রিটার্ন করুন

বেশি বুঝতে নিচের বাস্তবায়নটি দেখুন:

উদাহরণ

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

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

class Solution:
    def solve(self, root):
        if not root:
            return 0
        self.maxPath = 0
        def helper(node):
            inc, dec = 1, 1
            if node.left:
                left_inc, left_dec = helper(node.left)
            else:
                left_inc, left_dec = 0, 0
            if node.right:
                right_inc, right_dec = helper(node.right)
            else:
                right_inc, right_dec = 0, 0
            if node.left and node.val - node.left.val == 1:
                inc = max(inc, left_inc + 1)
            elif node.left and node.val - node.left.val == -1:
                dec = max(dec, left_dec + 1)
            if node.right and node.val - node.right.val == 1:
                inc = max(inc, right_inc + 1)
            elif node.right and node.val - node.right.val == -1:
                dec = max(dec, right_dec + 1)
            if (node.left and node.right and
                node.left.val - node.val == 1 and node.val - node.right.val == 1):
                self.maxPath = max(self.maxPath, left_dec + right_inc + 1)
            elif (node.left and node.right and
                  node.left.val - node.val == -1 and node.val - node.right.val == -1):
                self.maxPath = max(self.maxPath, left_inc + right_dec + 1)
            self.maxPath = max(self.maxPath, inc, dec)
            return inc, dec
        helper(root)
        return self.maxPath

ob = Solution()
root = TreeNode(3)
root.left = TreeNode(2)
root.right = TreeNode(4)
root.right.left = TreeNode(5)
root.right.right = TreeNode(9)
root.right.left.left = TreeNode(6)
print(ob.solve(root))

ইনপুট

root = TreeNode(3) root.left = TreeNode(2) root.right = TreeNode(4) root.right.left = TreeNode(5) root.right.right = TreeNode(9) root.right.left.left = TreeNode(6)

আউটপুট

5