दोनों ट्रीज़ के लीफ नोड्स (ऑपरेंड्स) की फ्रीक्वेंसी काउंट करके तुलना करें: अगर समान तो ट्रीज़ इक्विवेलेंट हैं।
एल्गोरिदम
- DFS से प्रत्येक ट्री के लीफ नोड्स (ऑपरेंड्स) की फ्रीक्वेंसी
Counterमें गिनें। - दोनों काउंटर्स तुलना करें:
dic1 == dic2। - ऑपरेटर्स को इग्नोर करें, केवल ऑपरेंड्स मैटर करते हैं (कम्यूटेटिव ऑपरेशन्स के लिए)।
उदाहरण कोड
import collections
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def solve(root1, root2):
dic1 = collections.defaultdict(int)
dic2 = collections.defaultdict(int)
def dfs(node, dic):
if not node: return
if not node.left and not node.right:
dic[node.val] += 1
dfs(node.left, dic)
dfs(node.right, dic)
dfs(root1, dic1)
dfs(root2, dic2)
return dic1 == dic2
# टेस्ट: ट्री1: (1+2)*(3+4), ट्री2: (2+1)*(4+3) -> दोनों इक्विवेलेंट -> True
इनपुट/आउटपुट
इनपुट: रूट1 = [1, '+', 2, '*', 3, '+', 4], रूट2 = [2, '+', 1, '*', 4, '+', 3]
आउटपुट: True
