মান ল করুন ০, ১ এবং ২ মান ধারণকারী একটি বাইনারি ট্রি। রুটে কমপক্ষে একটি ০ নোড এবং একটি ১ নোড আছে। এখন একটি অপারেশন আছে যেখানে ট্রির একটি এজ মুছে ফেললে ট্রি দুটি আলাদা ট্রিতে ভাগ হয়ে যায়। আমাদের খুঁজে বের করতে হবে কতভাবে একটি এজ মুছে ফেলা যায় যাতে দুটি ট্রির যেকোনো একটি ০ এবং ১ নোড দুটি একসাথে না থাকে।
যদি ইনপুট হয়:
তবে আউটপুট হবে ১ কারণ শুধু ০ থেকে ২ এজটি মুছে ফেলা যায়।
এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব:
- count := [0, 0, 0]
- একটি dfs() ফাংশন সংজ্ঞায়িত করুন। এটি node গ্রহণ করবে।
- যদি node null না হয়:
- pre := count
- dfs(node.left), dfs(node.right)
- count[node.val] := count[node.val] + 1
- node.count := [count[i] - pre[i] for i in range(2)]
- একটি dfs2() ফাংশন সংজ্ঞায়িত করুন। এটি node, par গ্রহণ করবে।
- যদি node null না হয়:
- যদি par null না হয়:
- (a0, a1) := node.count
- (b0, b1) := (count[0] - a0, count[1] - a1)
- যদি (a0 == 0 or a1 == 0) and (b0 == 0 or b1 == 0), ans := ans + 1
- dfs2(node.left, node), dfs2(node.right, node)
- যদি par null না হয়:
- মূল মেথড থেকে: dfs(root), ans := 0, dfs2(root), ans ফেরত দিন।
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশনটি দেখুন:
উদাহরণ
class TreeNode: def __init__(self, data, left = None, right = None): self.val = data self.left = left self.right = right class Solution: def solve(self, root): count = [0, 0, 0] def dfs(node): if node: pre = count[:] dfs(node.left) dfs(node.right) count[node.val] += 1 node.count = [count[i] - pre[i] for i in range(2)] dfs(root) def dfs2(node, par=None): if node: if par is not None: a0, a1 = node.count b0, b1 = count[0] - a0, count[1] - a1 if (a0 == 0 or a1 == 0) and (b0 == 0 or b1 == 0): self.ans += 1 dfs2(node.left, node) dfs2(node.right, node) self.ans = 0 dfs2(root) return self.ans ob = Solution() root = TreeNode(0) root.left = TreeNode(0) root.right = TreeNode(2) root.right.left = TreeNode(1) root.right.right = TreeNode(1) print(ob.solve(root))
ইনপুট
root = TreeNode(0) root.left = TreeNode(0) root.right = TreeNode(2) root.right.left = TreeNode(1) root.right.right = TreeNode(1)
আউটপুট
1
