Pythonでノードを交換することで2つのツリーを形成できるかどうかを確認するプログラム

2つのツリーがあるとすると、ノードの左右のサブツリーを何度でも交換して、最初のツリーを2番目のツリーに変換できるかどうかを確認する必要があります。

したがって、入力が次のような場合

その場合、出力はTrueになります

これを解決するには、次の手順に従います-

• que1：=最初はroot0のキュー

• que2：=最初はroot1のキュー

• que1とque2は空ではありませんが、実行してください

  • temp1：=新しいリスト、temp2：=新しいリスト

  • values1：=新しいリスト、values2：=新しいリスト

  • que1とque2に含まれる要素の数が異なる場合は、

    • Falseを返す

  • 範囲0からque1− 1のサイズのiの場合、実行

    • values1の最後にque1[i]の値を挿入します

    • values2の最後にque2[i]の値を挿入します

    • que1 [i]の権利がnullでない場合、

      • temp1の最後にque1[i]の右側を挿入します

    • que1 [i]の左側がnullでない場合、

      • temp1の最後にque1[i]の左側を挿入します

    • que2 [i]の権利がnullでない場合、

      • temp2の最後にque2[i]の右側を挿入します

    • que2 [i]の左側がnullでない場合、

      • temp2の最後にque2[i]の左側を挿入します

  • 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