मान लीजिए हमारे पास एक बाइनरी ट्री है जिसमें 0, 1 और 2 मान हैं। रूट में कम से कम एक 0 नोड और एक 1 नोड है। अब मान लीजिए एक ऑपरेशन है जहां हम ट्री में एक किनारा हटाते हैं और ट्री दो अलग-अलग ट्री बन जाता है। हमें उन तरीकों की संख्या ढूंढनी है जिनसे हम एक किनारा हटा सकते हैं जैसे कि दोनों ट्री में से कोई भी 0 नोड और 1 नोड दोनों को न रखे।
इसलिए, यदि इनपुट इस तरह है

तो आउटपुट 1 होगा क्योंकि हम केवल 0 से 2 किनारे को हटा सकते हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −
- count := [0, 0, 0]
- एक फ़ंक्शन dfs() परिभाषित करें। यह node लेगा
- यदि node null नहीं है, तो
- pre := count
- dfs(node का बायाँ)
- dfs(node का दायाँ)
- count[node का मान] := count[node का मान] + 1
- node.count := i के लिए (count[i] - pre[i]) की सूची जहां i 0 और 1 है
- एक फ़ंक्शन dfs2() परिभाषित करें। यह node, par लेगा
- यदि node null नहीं है, तो
- यदि par null नहीं है, तो
- (a0, a1) := node का count
- (b0, b1) := (count[0] - a0, count[1] - a1)
- यदि (a0, 0 के समान है या a1, 0 के समान है) और (b0, 0 के समान है या b1, 0 के समान है), तो
- ans := ans + 1
- dfs2(node का बायाँ, node)
- dfs2(node का दायाँ, 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