在Python中编写的计算二叉树分成两棵树的方案数程序

假设我们有一个包含值0、1和2的二叉树。根至少有一个0节点和一个1节点。现在假设有一种操作，我们删除树中的一条边，树就变成了两个不同的树。我们必须找到一种删除一条边的方法，以使这两颗树都不包含0节点和1节点。

因此，如果输入如下所示：

那么输出将是1，因为我们只能删除从0到2的边缘。

为了解决这个问题，我们将按照以下步骤进行操作−

• count：= [0,0,0]
• 定义函数dfs()。这将接收节点
• 如果节点不为空，则
  • pre：=计数
  • dfs(node的左侧)
  • dfs(node的右侧)
  • count[node的值]：= count[node的值] + 1
  • node.count：为i为0和1的(count[i]-pre[i])的列表
• 定义函数dfs2()。这将接收节点，par
• 如果节点不为空，则
  • 如果par不为空，则
    • (a0,a1)：=节点的计数
    • (b0,b1)：=（计数[0]−a0，计数[1]−a1）
    • 如果(a0等于0或a1等于0)且(b0等于0或b1等于0)，则
    • answer：= answer + 1
  • dfs2(node的左侧，node)
  • dfs2(node的右侧，node)
• 从主方法中，执行以下操作−
• dfs(root)
• answer：=0
• dfs2(root)
• 返回answer

让我们看看以下的实现，以更好地理解−

更多Python相关文章，请阅读：Python 教程

例子

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