algorithm - ツリーに代替プロパティがあるかどうかを確認する

Question

ツリーの各ノードが白または黒のいずれかであるツリーが存在し、内部ノードごとに、その子がその内部ノードの反対の色であるとします。したがって、ツリーがスケッチされている場合、「最上位」は (たとえば) 黒いノードで構成され、次のレベルはすべて白いノード、次のレベルはすべて黒いノード、というようになります。

ルート x を持つツリーが与えられた場合、そのツリーがこれらの基準を満たしているかどうかを確認できるアルゴリズムは存在しますか?

Answer 1

はい。再帰的な深さ優先トラバーサルは、これをかなり簡単に行う必要があります。すべての子の色が異なること、およびこのチェッカー関数が呼び出されたときにすべての子が true を返すことをチェックするメソッドを各ノードに配置します。

Answer 2

dept first search を使用すると、現在アクセスしているノードの dept を簡単に知ることができます。次に、ルート ノードの値に基づいて、現在のノードを黒にする必要があるか白にする必要があるかを簡単に確認できます。

ルートが黒の場合 (ルートの深さが 0 に設定されている場合)、すべての偶数の深さノードは黒で、奇数の深さノードは白である必要があり、白のルートの場合はその逆です。

ツリーが基準を満たしていることを確認するには、すべてのノードにアクセスする必要があることに注意してください。したがって、可能な限り最適な複雑さは O(n) です。