Python程序检查两棵树是否可以通过交换节点形成

假设我们有两棵树，我们需要检查是否可以通过任意次数交换任何节点的左右子树来将第一棵树转换为第二棵树。

所以，如果输入如下所示

则输出为 True

为了解决这个问题，我们将遵循以下步骤：

  • que1 := 初始值为 root0 的队列

  • que2 := 初始值为 root1 的队列

  • 当 que1 和 que2 不为空时，执行以下操作

    • temp1 := 新列表，temp2 := 新列表

    • values1 := 新列表，values2 := 新列表

    • 如果 que1 和 que2 包含不同数量的元素，则

      • 返回 False

    • 对于范围从 0 到 que1 大小减 1 的 i，执行以下操作

      • 将 que1[i] 的值插入到 values1 的末尾

      • 将 que2[i] 的值插入到 values2 的末尾

      • 如果 que1[i] 的右子节点不为空，则

        • 将 que1[i] 的右子节点插入到 temp1 的末尾

      • 如果 que1[i] 的左子节点不为空，则

        • 将 que1[i] 的左子节点插入到 temp1 的末尾

      • 如果 que2[i] 的右子节点不为空，则

        • 将 que2[i] 的右子节点插入到 temp2 的末尾

      • 如果 que2[i] 的左子节点不为空，则

        • 将 que2[i] 的左子节点插入到 temp2 的末尾

    • 如果 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

更新于： 2020-10-21

113 次浏览

开启你的 职业生涯

通过完成课程获得认证

立即开始
广告