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.