判断两棵二叉树是否同构

先给最常规意义上的解法,按照二叉树同构的严格定义:

  • 遍历所有的节点,如果值相同,且左子树同构,且右子树同构,这两棵树同构;
def is_same(node1, node2):
    return all([
        node1.value == node2.value,
        is_same(node1.left, node2.left),
        is_same(node1.right, node2.right),
        ])

再给另外一个方案:

def is_same(tree1, tree2):
    return tree_hash(tree1) == tree_hash(tree2)

这个方案中的如果计算树的散列值是个不大不小的问题,最简单的是将树表示为一个字串。例如:node(1, (node2(1, None, None), node3(3, None, node4(3, None, None))),再对这个字串取哈希值。

Advertisements
此条目发表在未分类分类目录,贴了标签。将固定链接加入收藏夹。

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s