Python程式：檢查是否可以對樹進行著色，使其相鄰節點顏色不同

假設我們有一棵二叉樹，其中每個節點的值代表其顏色。樹中最多有兩種顏色。我們必須檢查是否可以透過任意次數交換節點的顏色，使得任何兩個相連的節點顏色不同。

因此，如果輸入如下：

則輸出為True，因為我們可以得到：

為了解決這個問題，我們將遵循以下步驟：

  • colors := 一個空對映
  • prop := 一個空對映
  • 定義一個函式dfs()。它將接受節點和標誌作為引數。
  • 如果節點為空，則
    • 返回
  • colors[節點的值] := colors[節點的值] + 1
  • prop[標誌] := prop[標誌] + 1
  • dfs(節點的左子節點, 標誌的反義)
  • dfs(節點的右子節點, 標誌的反義)
  • 在主方法中執行以下操作：
  • dfs(根節點, true)
  • 當colors和prop中的所有元素都相同時返回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

更新於：2020年12月2日

瀏覽量：183

啟動您的職業生涯

完成課程獲得認證

開始學習
廣告
© . All rights reserved.