पायथन में नोड्स की अदला-बदली से दो पेड़ बन सकते हैं या नहीं, इसकी जाँच करने के लिए कार्यक्रम

मान लीजिए कि हमारे पास दो पेड़ हैं, हमें यह जांचना होगा कि क्या हम किसी भी नोड के बाएँ और दाएँ सबट्री को कितनी भी बार स्वैप करके पहले पेड़ को दूसरे में बदल सकते हैं।

तो, अगर इनपुट पसंद है

तो आउटपुट सही होगा

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

que1 :=शुरुआत में root0 वाली एक कतार
que2 :=शुरुआत में root1 वाली एक कतार
जबकि que1 और que2 खाली नहीं हैं, करें
- temp1:=एक नई सूची, temp2:=एक नई सूची
- value1 :=एक नई सूची, value2 :=एक नई सूची
- यदि que1 और que2 में अलग-अलग संख्या में तत्व हैं, तो
  - झूठी वापसी
- मैं के लिए 0 से लेकर que1 − 1 के आकार तक के लिए, करें
  - मान 1 के अंत में que1[i] का मान डालें
  - value2 के अंत में que2[i] का मान डालें
  - यदि que1[i] का दायां अशक्त नहीं है, तो
    - temp1 के अंत में que1[i] के दाईं ओर डालें
  - यदि que1[i] का बायां भाग रिक्त नहीं है, तो
    - temp1 के अंत में que1[i] के बाईं ओर डालें
  - यदि que2[i] का दायां अशक्त नहीं है, तो
    - temp2 के अंत में que2[i] के दाईं ओर डालें
  - यदि que2[i] का बायां भाग रिक्त नहीं है, तो
    - temp2 के अंत में que2[i] के बाईं ओर डालें
- यदि मान1 मान 2 के समान नहीं है, तो
  - यदि Value1 विपरीत क्रम में मान 2 के समान नहीं है, तो
    - झूठी वापसी
- que1 :=temp1, que2 :=temp2
सही लौटें

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

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