Pythonでツリーを2つのツリーに分割できる方法の数を数えるプログラム

値0、1、および2を含む二分木があるとします。ルートには少なくとも1つの0ノードと1つの1ノードがあります。ここで、ツリーのエッジを削除し、ツリーが2つの異なるツリーになる操作があるとします。 2つのツリーのいずれにも0ノードと1ノードの両方が含まれないように、1つのエッジを削除できる方法の数を見つける必要があります。

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

0から2のエッジしか削除できないため、出力は1になります。

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

• count：=[0、0、0]
• 関数dfs（）を定義します。これはノードを取ります
• ノードがnullでない場合、
  • pre：=count
  • dfs（ノードの左側）
  • dfs（ノードの右側）
  • count [ノードの値]：=count[ノードの値]+1
  • node.count：=iの（count [i] --pre [i]）のリストは0と1です
• 関数dfs2（）を定義します。これはノード、パーを取ります
• ノードがnullでない場合、
  • parがnullでない場合、
    • （a0、a1）：=ノードの数
    • （b0、b1）：=（count [0] --a0、count [1] --a1）
    • （a0が0と同じ、またはa1が0と同じ）かつ（b0が0と同じ、またはb1が0と同じ）の場合、
      • ans：=ans + 1
  • dfs2（ノードの左側、ノード）
  • dfs2（ノードの右側、ノード）
• メインの方法から、次の手順を実行します-
• dfs（root）
• ans：=0
• dfs2（root）
• 回答を返す

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

例

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):
      count = [0, 0, 0]
   def dfs(node):
      if node:
         pre = count[:]
         dfs(node.left)
         dfs(node.right)
         count[node.val] += 1
         node.count = [count[i] - pre[i] for i in range(2)]
   dfs(root)
   def dfs2(node, par=None):
      if node:
         if par is not None:
            a0, a1 = node.count
            b0, b1 = count[0] - a0, count[1] - a1
            if (a0 == 0 or a1 == 0) and (b0 == 0 or b1 == 0):
               self.ans += 1
         dfs2(node.left, node)
         dfs2(node.right, node)
   self.ans = 0
   dfs2(root)
   return self.ans
ob = Solution()
root = TreeNode(0)
root.left = TreeNode(0)
root.right = TreeNode(2)
root.right.left = TreeNode(1)
root.right.right = TreeNode(1)
print(ob.solve(root))

入力

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

出力

1