Pythonで隣接するノードが同じ色を持たないツリーに色を付けることができるかどうかを確認するプログラム

各ノードの値がその色を表す二分木があるとします。木にはせいぜい2色しかありません。接続されている2つのノードが同じ色にならないように、ノードの色を何度でも交換できるかどうかを確認する必要があります。

したがって、入力が次のような場合

そうすれば、出力はTrueになります

これを解決するには、次の手順に従います-

• 色：=空の地図
• prop：=空のマップ
• 関数dfs（）を定義します。これはノードを取り、フラグを立てます
• ノードがnullの場合、
  • 戻る
• 色[ノードの値]：=色[ノードの値] + 1
• prop [flag]：=prop [flag] + 1
• dfs（ノードの左側、フラグの逆）
• dfs（ノードの右側、フラグの逆）
• メインの方法から次の手順を実行します。
• dfs（root、true）
• 色と小道具のすべての要素が同じ場合はtrueを返し、それ以外の場合はfalseを返します

理解を深めるために、次の実装を見てみましょう-

例

from collections import defaultdict
class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.val = data
      self.left = left
      self.right = right

class Solution:
   def solve(self, root):
      colors = defaultdict(int)
      prop = defaultdict(int)

      def dfs(node, flag=True):
         if not node:
            return
         colors[node.val] += 1
         prop[flag] += 1
         dfs(node.left, not flag)
         dfs(node.right, not flag)

      dfs(root)
      return set(colors.values()) == set(prop.values())
     
ob = Solution()
root = TreeNode(2)
root.left = TreeNode(2)
root.right = TreeNode(2)
root.right.left = TreeNode(1)
root.right.right = TreeNode(1)
root.right.left.right = TreeNode(1)
print(ob.solve(root))

入力

root = TreeNode(2)
root.left = TreeNode(2)
root.right = TreeNode(2)
root.right.left = TreeNode(1)
root.right.right = TreeNode(1)
root.right.left.right = TreeNode(1)

出力

True