Python 檢查兩棵樹的所有層級是否互為字謎

假設我們有兩個二叉樹。我們必須檢查每個二叉樹的每一層是否都是另一個二叉樹相同層的字謎。如果是字謎，則返回 True，否則返回 False。

因此，如果輸入如下所示：

，則輸出將為 True。

為了解決這個問題，我們將遵循以下步驟：

  • tree_1 是第一棵樹的根節點，tree_2 是第二棵樹的根節點。
  • 如果 tree_1 等於 null 且 tree_2 等於 null，則
    • 返回 True
  • 如果 tree_1 等於 null 或 tree_2 等於 null，則
    • 返回 False
  • queue1 := 一個新的佇列
  • queue2 := 一個新的佇列
  • 將 tree_1 插入 queue1 的末尾
  • 將 tree_2 插入 queue2 的末尾
  • 當 1 非零時，執行以下操作：
    • size1 := queue1 的大小
    • size2 := queue2 的大小
    • 如果 size1 不等於 size2，則
      • 返回 False
    • 如果 size1 等於 0，則
      • 退出迴圈
    • curr_level1 := 一個新的列表
    • curr_level2 := 一個新的列表
    • 當 size1 > 0 時，執行以下操作：
      • node1 := queue1 的第一個元素
      • 從 queue1 刪除第一個元素
      • 如果 node1 的左子節點不等於 null，則
        • 將 node1 的左子節點插入 queue1 的末尾
      • 如果 node1 的右子節點不等於 null，則
        • 將 node1 的右子節點插入 queue1 的末尾
      • size1 := size1 - 1
      • node2 := queue2 的第一個元素
      • 從 queue2 刪除第一個元素
      • 如果 node2 的左子節點不等於 null，則
        • 將 node2 的左子節點插入 queue2 的末尾
      • 如果 node2 的右子節點不等於 null，則
        • 將 node2 的右子節點插入 queue2 的末尾
      • 將 node1 的值插入 curr_level1 的末尾
      • 將 node2 的值插入 curr_level2 的末尾
    • 對列表 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

更新於：2021年1月18日

161 次瀏覽

開啟您的職業生涯

透過完成課程獲得認證

開始學習
廣告
© . All rights reserved.