파이썬에서 인접한 노드가 같은 색을 가지지 않는 나무를 색칠할 수 있는지 확인하는 프로그램

각 노드의 값이 색상을 나타내는 이진 트리가 있다고 가정합니다. 트리에는 최대 2가지 색상이 있습니다. 연결된 두 노드의 색상이 동일하지 않도록 노드의 색상을 여러 번 바꿀 수 있는지 확인해야 합니다.

따라서 입력이 다음과 같으면

그러면 우리가 얻을 수 있는 대로 출력이 True가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 색상 :=빈 지도
• prop :=빈 지도
• dfs() 함수를 정의합니다. 노드 및 플래그가 필요합니다.
• 노드가 null이면
  • 반환
• 색상[노드 값] :=색상[노드 값] + 1
• 소품[플래그] :=소품[플래그] + 1
• dfs(노드의 왼쪽, 플래그의 반대)
• dfs(노드의 오른쪽, 플래그의 반대)
• 기본 방법에서 다음을 수행합니다.
• dfs(루트, 참)
• 색상과 소품의 모든 요소가 같으면 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