मान लीजिए हमारे पास दो ट्री हैं, हमें यह जांचना है कि क्या हम पहले ट्री को दूसरे में किसी भी नोड के बाएं और दाएं सबट्री को कितनी भी बार स्वैप करके बदल सकते हैं।
तो, यदि इनपुट इस तरह है
तो आउटपुट True होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
- que1 := root0 के साथ प्रारंभ एक कतार
- que2 := root1 के साथ प्रारंभ एक कतार
- जब तक que1 और que2 खाली नहीं हैं, करें
- temp1 := एक नई सूची, temp2 := एक नई सूची
- values1 := एक नई सूची, values2 := एक नई सूची
- यदि que1 और que2 में अलग-अलग संख्या में तत्व हैं, तो False लौटाएं
- i को 0 से que1 के आकार - 1 तक की रेंज में लिए, करें
- que1[i] का मान values1 के अंत में डालें
- que2[i] का मान values2 के अंत में डालें
- यदि que1[i] का दाएं null नहीं है, तो que1[i] के दाएं को temp1 के अंत में डालें
- यदि que1[i] का बाएं null नहीं है, तो que1[i] के बाएं को temp1 के अंत में डालें
- यदि que2[i] का दाएं null नहीं है, तो que2[i] के दाएं को temp2 के अंत में डालें
- यदि que2[i] का बाएं null नहीं है, तो que2[i] के बाएं को temp2 के अंत में डालें
- यदि values1, values2 के समान नहीं है, तो
- यदि values1, values2 के रिवर्स क्रम के समान नहीं है, तो False लौटाएं
- que1 := temp1, que2 := temp2
- True लौटाएं
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
उदाहरण
class TreeNode:
def __init__(self, data, left=None, right=None):
self.val = data
self.left = left
self.right = right
class Solution:
def solve(self, root0, root1):
que1 = [root0]
que2 = [root1]
while que1 and que2:
temp1 = []
temp2 = []
values1 = []
values2 = []
if len(que1) != len(que2):
return False
for i in range(len(que1)):
values1.append(que1[i].val)
values2.append(que2[i].val)
if que1[i].right:
temp1.append(que1[i].right)
if que1[i].left:
temp1.append(que1[i].left)
if que2[i].right:
temp2.append(que2[i].right)
if que2[i].left:
temp2.append(que2[i].left)
if values1 != values2:
if values1 != values2[::-1]:
return False
que1 = temp1
que2 = temp2
return True
ob = Solution()
root = TreeNode(2)
root.right = TreeNode(4)
root.right.left = TreeNode(3)
root.right.right = TreeNode(5)
root1 = TreeNode(2)
root1.left = TreeNode(4)
root1.left.left = TreeNode(3)
root1.left.right = TreeNode(5)
print(ob.solve(root, root1))
इनपुट
root = TreeNode(2)
root.right = TreeNode(4)
root.right.left = TreeNode(3)
root.right.right = TreeNode(5)
root1 = TreeNode(2)
root1.left = TreeNode(4)
root1.left.left = TreeNode(3)
root1.left.right = TreeNode(5)आउटपुट
True
