时间戳

首页 > 解决方案 > 检查树是否对称（关于其中心）可能不使用类

python-3.x - 检查树是否对称（关于其中心）可能不使用类

问题描述

我一直看到算法（例如this或this）进行对称树检查，但它们总是迎合二叉树。该算法本质上是：使用两个变量（指针），它们在遍历时保持关于中心对称，如果在任何点，它们不对应于相同的 node_value，则返回 False。最后，返回 True。

所以给定一个邻接列表（输入可以是 V 表示顶点的数量，然后是 (u,v) 对表示 u -> v 的边），我如何实现通用树的算法？一个不需要类概念的人会帮助我，除非不可能这样做。至于树的定义，假设将给定根节点作为输入，并且输入元素的顺序将代表子节点的顺序。例如，[[..],[..],[1,4,3],[..]] 对应于 node_2 有三个孩子 1,4,3，其中 node_1 是最左边的孩子，node_4 是中间的孩子一和 node_3 最右边的孩子。

我更愿意获得用 Python 编写代码的帮助；否则伪代码（至少是实现的粗略草图）会有所帮助，我会用谷歌搜索必要的东西。

标签： python-3.xalgorithmtreegraph-algorithm

解决方案

让我们以这棵树为例。节点由一个数字标识：

            _________0_________
           /         |         \
          1          2          3
         / \       / | \       / \  
        4   5    6   7   8    9   10
        |       / \     / \        |
       11      12 13   14 15      16

这可以在以下邻接列表中编码（有向边“向下”）：

adj = [
    [1, 2, 3],
    [4, 5],
    [6, 7, 8],
    [9, 10],
    [11],
    [],
    [12, 13],
    [],
    [14, 15],
    [],
    [16],
    [],
    [],
    [],
    [],
    [],
    []
]

一种方法是创建一个执行深度优先遍历的生成器，当它在树中下降时产生 1，当它上升时产生 2。当遍历完成时，它可能会产生 3：

def dfs(adj, sense=1, root=0):
    for child in adj[root][::sense]:
        yield 1  # Indicate that we move down in the tree
        yield from dfs(adj, sense, child)  # recurse...
        yield 2  # Indicate that we up up in the tree
    yield 3  # Indicate that we arrived back at the root.

实际值 1、2 和 3 可自由选择。唯一的要求是它们彼此不同。

该sense参数确定是按正确的顺序（“从左到右”）还是以相反的顺序（“从右到左”）遍历子级。

有了这个，很容易检查树是否对称。串联执行两个相反方向的遍历，每次都验证两个遍历中的下一个产生的值是否相同：

def is_symmetric(adj, root=0):
    a_iter = dfs(adj, 1, root)  # get iterator for the "left-to-right" traversal
    for b in dfs(adj, -1, root):  # traverse "right-to-left"
        if b != next(a_iter):  # verify that both traversals give the same value
            return False
    return True

使用zip并且all您可以将该函数编写为：

def is_symmetric(adj, root=0):
    return all(a == b for a, b in zip(dfs(adj, 1, root), dfs(adj, -1, root)))

当一棵树的节点比另一棵树的节点少时，不存在未检测到差异的风险，因为那时a或b将在某个点获得值 3，与来自另一棵树的 1 或 2 不同。因此all将返回 False。

调用函数如下：

print(is_symmetric(adj))  # True for the example above.

推荐阅读