পাইথনে রুট-টু-লিফ পাথে ইনসাফিশিয়েন্ট নোড রিমুভ করা

মনে করুন আমাদের একটি বাইনারি ট্রি আছে। একটি নোড ইনসাফিশিয়েন্ট যদি সেই নোডকে ছেদ করে যাওয়া সকল রুট-টু-লিফ পাথের সম স্ট্রিক্টলি limit-এর চেয়ে কম হয়। আমাদের সকল ইনসাফিশিয়েন্ট নোড একসাথে ডিলিট করে ফলাফল বাইনারি ট্রির রুট রিটার্ন করতে হবে।

ট্রি যদি নিচের মতো হয়, এবং limit = 1:

তবে আউটপুট ট্রি হবে:

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

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

  • যদি নোডের বাম ও ডান সাবট্রি না থাকে (লিফ নোড):

    • যদি root.val < limit, তবে None রিটার্ন করুন, অন্যথায় root।

  • যদি বাম সাবট্রি থাকে, তবে root.left = solve(root.left, limit - root.val)

  • যদি ডান সাবট্রি থাকে, তবে root.right = solve(root.right, limit - root.val)

  • যদি নোডের বাম বা ডান যেকোনো একটি সাবট্রি থাকে, তবে root রিটার্ন করুন, অন্যথায় None।

উদাহরণ

class Solution(object):
    def sufficientSubset(self, root, limit):
        """
        :type root: TreeNode
        :type limit: int
        :rtype: TreeNode
        """
        if not root.left and not root.right:
            return None if root.val < limit else root
        if root.left:
            root.left = self.sufficientSubset(root.left, limit - root.val)
        if root.right:
            root.right = self.sufficientSubset(root.right, limit - root.val)
        return root if root.left or root.right else None

ইনপুট

[1,2,3,4,-99,-99,7,8,9,-99,-99,12,13,-99,14] 1

আউটপুট

[1,2,3,4,null,null,7,8,9,null,14]