2つのツリーのすべてのレベルがアナグラムであるかどうかをPythonで確認します

2つの二分木が提供されているとします。二分木の各レベルが他の二分木の同じレベルのアナグラムであるかどうかを確認する必要があります。アナグラムの場合はTrueを返し、そうでない場合はFalseを返します。

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

、出力はTrueになります。

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

• tree_1は最初のツリーのルートノードであり、tree_2は2番目のツリーのルートノードです。
• tree_1がnullと同じで、tree_2がnullと同じ場合、
  • Trueを返す
• tree_1がnullと同じであるか、tree_2がnullと同じである場合、
  • Falseを返す
• queue1：=新しいキュー
• queue2：=新しいキュー
• queue1の最後にtree_1を挿入します
• queue2の最後にtree_2を挿入します
• 1がゼロ以外の場合は、
  • size1：=queue1のサイズ
  • size2：=queue2のサイズ
  • size1がsize2と同じでない場合、
    • Falseを返す
  • size1が0と同じ場合、
    • ループから抜け出す
  • curr_level1：=新しいリスト
  • curr_level2：=新しいリスト
  • size1> 0の場合、実行
    • node1：=queue1の最初の要素
    • queue1から最初の要素を削除します
    • node1の左側がnullと同じでない場合、
      • queue1の最後にnode1の左側を挿入します
    • node1の権利がnullと同じでない場合、
      • queue1の最後にnode1の右側を挿入します
    • size1：=size1-1
    • node2：=queue2の最初の要素
    • queue2から最初の要素を削除する
    • node2の左側がnullと同じでない場合、
      • queue2の最後にnode2の左側を挿入します
    • node2の権利がnullと同じでない場合、
      • queue2の最後にnode2の右側を挿入します
    • curr_level1の最後にnode1の値を挿入します
    • curr_level2の最後にnode2の値を挿入します
  • リストcurr_level1を並べ替える
  • リストcurr_level2を並べ替える
  • curr_level1がcurr_level2と同じでない場合、
    • Falseを返す
• Trueを返す

例

理解を深めるために、次の実装を見てみましょう-

def make_tree(elements):
   tree = tree_node(elements[0])
   for element in elements[1:]:
      insert_value(tree, element)
   return tree
def insert_value(temp,value):
   que = []
   que.append(temp)
   while (len(que)):
      temp = que[0]
      que.pop(0)
      if (not temp.left):
         if value is not None:
            temp.left = tree_node(value)
         else:
            temp.left = tree_node(0)
         break
      else:
         que.append(temp.left)
      if (not temp.right):
         if value is not None:
            temp.right = tree_node(value)
         else:
            temp.right = tree_node(0)
         break
      else:
         que.append(temp.right)
class tree_node:
   def __init__(self, value):
      self.value = value
      self.left = None
      self.right = None
def solve(tree_1, tree_2) :
   if (tree_1 == None and tree_2 == None) :
      return True
   if (tree_1 == None or tree_2 == None) :
      return False
   queue1 = []
   queue2 = []
   queue1.append(tree_1)
   queue2.append(tree_2)
   while (1) :
      size1 = len(queue1)
      size2 = len(queue2)
      if (size1 != size2):
         return False
      if (size1 == 0):
         break
      curr_level1 = []
      curr_level2 = []
      while (size1 > 0):
         node1 = queue1[0]
         queue1.pop(0)
         if (node1.left != None) :
            queue1.append(node1.left)
         if (node1.right != None) :
            queue1.append(node1.right)
         size1 -= 1
         node2 = queue2[0]
         queue2.pop(0)
         if (node2.left != None) :
            queue2.append(node2.left)
         if (node2.right != None) :
            queue2.append(node2.right)
         curr_level1.append(node1.value)
         curr_level2.append(node2.value)
      curr_level1.sort()
      curr_level2.sort()
      if (curr_level1 != curr_level2) :
         return False
   return True
tree_1 = make_tree([5, 6, 7, 9, 8])
tree_2 = make_tree([5, 7, 6, 8, 9])
print(solve(tree_1, tree_2))

入力

[5, 6, 7, 9, 8], [5, 7, 6, 8, 9]

出力

True