二叉树同构迭代

Question

我想知道是否有一种方法可以迭代地检查两个二叉树是否彼此同构（事实上，我们都知道递归的问题），到目前为止，这是我找到的最好的解决方案： https://github.com/deepwritescode/isomorph#iterative.

但是，我想删除节点值的检查条件；因为我需要的应该仅限于检查树的结构，而不是它们在节点内的实际值...... 每种语言都被接受。

P.S.：这个实现也不起作用：https://www.geeksforgeeks.org/iterative-approach-to-check-if-two-binary-trees-are-isomorphic-or-not/

Answer 1

正如所引用的来源所建议的那样，您可以在两棵树上使用级别顺序遍历，同时生成空值以指示不存在孩子。当串联遍历两棵树时，一侧给出空值，而另一侧没有，树不是同构的。

这里是Python中的解决方案代码，使用生成器进行这样的层序遍历：

from collections import deque

class node:
    def __init__(self, left=None, right=None):
        self.left = left
        self.right = right

def levelorder(root):
    q = deque()
    q.append(root)
    while q:
        node = q.popleft()
        yield node
        if node:
            q.append(node.left)
            q.append(node.right)
        
def isIsomorphic(root1, root2):
    return all((not node1) == (not node2) for node1, node2 in zip(levelorder(root1), levelorder(root2)))

# Create tree: just a shape, no values
root1 = node(
    node(
        node(),
        node(
            node(),
            node()
        )
    ),
    node(
        node(),
        None
    )
)
# Second tree - same shape
root2 = node(
    node(
        node(),
        node(
            node(),
            node()
        )
    ),
    node(
        node(),
        None
    )
)

print (isIsomorphic(root1, root2))  # True