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

pythonserver side programmingprogramming更新于 2026/2/4 7:08:17

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

因此，如果输入如下

则输出将为 True

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

que1 := 最初为 root0 的队列
que2 := 最初为 root1 的队列最初
当 que1 和 que2 不为空时，执行
- temp1 := 一个新列表，temp2 := 一个新列表
- values1 := 一个新列表，values2 := 一个新列表
- 如果 que1 和 que2 包含不同数量的元素，则
  - 返回 False
- 对于 i，范围为 0 到 que1 的大小 − 1，执行
  - 在 values1 末尾插入 que1[i] 的值
  - 在 values2 末尾插入 que2[i] 的值
  - 如果 que1[i] 的右侧不为空，则
    - 在 temp1 末尾插入 que1[i] 的右侧
  - 如果 que1[i] 的左侧不为空，则
    - 在 temp1 末尾插入 que1[i] 的左侧
  - 如果 que2[i] 的右侧不为空，则
    - 插入 que2[i] 的右侧在 temp2 的末尾
  - 如果 que2[i] 的左侧不为空，则
    - 在 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)