求迭代法判断两棵二叉树结构同构的实现（无需检查节点值）

核心逻辑 #

二叉树结构同构指的是：可以通过交换任意节点的左右子树，让两棵树的结构完全重合。迭代实现用队列做层次遍历，每次成对处理两棵树的节点，只关注子树是否存在，完全不涉及节点值的校验。

Python 实现代码 #

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def is_structure_isomorphic(root1, root2):
    from collections import deque
    # 队列存储待配对处理的节点对
    node_queue = deque([(root1, root2)])

    while node_queue:
        n1, n2 = node_queue.popleft()

        # 两个节点都为空，符合结构要求，继续处理下一对
        if not n1 and not n2:
            continue
        # 一个空一个非空，结构肯定不同
        if not n1 or not n2:
            return False

        # 提取当前节点的子树存在状态
        n1_has_left = n1.left is not None
        n1_has_right = n1.right is not None
        n2_has_left = n2.left is not None
        n2_has_right = n2.right is not None

        # 检查结构匹配的两种可能：完全一致 或 左右镜像交换
        valid_match = (n1_has_left == n2_has_left and n1_has_right == n2_has_right) or \
                      (n1_has_left == n2_has_right and n1_has_right == n2_has_left)
        if not valid_match:
            return False

        # 根据匹配类型，将对应子节点对加入队列
        if n1_has_left == n2_has_left and n1_has_right == n2_has_right:
            node_queue.append((n1.left, n2.left))
            node_queue.append((n1.right, n2.right))
        else:
            node_queue.append((n1.left, n2.right))
            node_queue.append((n1.right, n2.left))

    return True

代码说明 #

1. 用队列同步遍历两棵树，确保每一步处理的是对应位置（或镜像位置）的节点
2. 只判断子树是否存在，完全跳过节点值的比较，满足忽略节点值的需求
3. 每一步都验证当前节点的子树组合是否与另一节点的子树组合匹配（要么完全一致，要么镜像），不匹配直接返回False
4. 所有节点对处理完成后无冲突，则返回True

测试示例 #

# 测试：结构完全一致（值不同但结构同构）
tree1 = TreeNode(1, TreeNode(2), TreeNode(3))
tree2 = TreeNode(10, TreeNode(20), TreeNode(30))
print(is_structure_isomorphic(tree1, tree2))  # 输出: True

# 测试：结构镜像（交换子树后同构）
tree3 = TreeNode(1, TreeNode(2, TreeNode(3)), None)
tree4 = TreeNode(5, None, TreeNode(6, TreeNode(7)))
print(is_structure_isomorphic(tree3, tree4))  # 输出: True

# 测试：结构不同
tree5 = TreeNode(1, TreeNode(2), None)
tree6 = TreeNode(1, TreeNode(2), TreeNode(3))
print(is_structure_isomorphic(tree5, tree6))  # 输出: False

内容的提问来源于stack exchange，提问作者James Deen