algorithm - 检查树是否具有交替属性

Question

假设存在一棵树，其中树的每个节点都是白色或黑色，并且对于每个内部节点，它的子节点是该内部节点的相反颜色。因此，如果绘制了树，它将具有“顶层”由（例如）一个黑色节点组成，然后是下一层所有白色节点，然后是下一层所有黑色节点，依此类推。

是否存在任何算法，给定具有根 x 的树，可以检查该树是否符合这些标准？

Answer 1

是的。递归深度优先遍历应该很容易做到这一点。在每个节点上放置一个方法，该方法检查其所有子节点是否具有不同的颜色，并且当对它们调用此检查器函数时，它的所有子节点是否返回 true。

Answer 2

使用 dept first search 很容易知道当前正在访问的节点的 dept。然后根据根节点的值，你可以很容易地检查当前节点是需要黑色还是白色：

如果根为黑色（并且根的深度设置为 0），则所有偶数深度节点都需要为黑色，奇数深度节点需要为白色，反之亦然。

请注意，您需要访问所有节点以验证树是否符合标准，因此最佳可能复杂度为 O(n)