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

মনে করুন আমাদের একটি বাইনারি ট্রির রুট দেওয়া আছে, প্রতিটি নোডের ইউনিক ভ্যালু রয়েছে। to_delete অ্যারেতে থাকা ভ্যালুয়ুক্ত সকল নোড রিমুভ করার পর আমাদের একটি ফরেস্ট (বন) পাওয়া যাবে। আমাদের অবশিষ্ট ফরেস্টের ট্রিগুলোর রুটগুলো রিটার্ন করতে হবে।

ইনপুট যদি নিচের মতো হয়:

to_delete = [3,5] হলে, আউটপুট হবে:

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

• res অ্যারে ডিফাইন করুন।

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

  • যদি node null হয়, তবে None রিটার্ন করুন।

  • flag := True যদি node.val to_delete-এ থাকে।

  • যদি flag == False এবং is_root == True, তবে node-কে res-এ অ্যাপেন্ড করুন।

  • node.left = solve(node.left, to_delete, flag)

  • node.right = solve(node.right, to_delete, flag)

  • return None if flag else node

• মেইন মেথড থেকে solve(root, to_delete, True) কল করুন।

উদাহরণ

class Solution(object):
    def delNodes(self, root, to_delete):
        """
        :type root: TreeNode
        :type to_delete: List[int]
        :rtype: List[TreeNode]
        """
        to_delete = set(to_delete)
        self.res = []
        self.solve(root, to_delete, True)
        return self.res

    def solve(self, node, to_delete, is_root):
        if not node:
            return None
        flag = node.val in to_delete
        if not flag and is_root:
            self.res.append(node)
        node.left = self.solve(node.left, to_delete, flag)
        node.right = self.solve(node.right, to_delete, flag)
        return None if flag else node

ইনপুট

[1,2,3,4,5,6,7] [3,5]

আউটপুট

[[1,2,null,4],[6],[7]]