Python程序：计算将树分成两棵树的方法数

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

因此，如果输入类似于

则输出将为1，因为我们只能删除0到2的边。

为了解决这个问题，我们将遵循以下步骤：

  • count := [0, 0, 0]
  • 定义一个函数dfs()。这将接受节点作为参数
  • 如果节点不为空，则
    • pre := count
    • dfs(节点的左子节点)
    • dfs(节点的右子节点)
    • count[节点的值] := count[节点的值] + 1
    • node.count := 一个列表，包含 (count[i] - pre[i])，其中 i 为 0 和 1
  • 定义一个函数dfs2()。这将接受节点和父节点作为参数
  • 如果节点不为空，则
    • 如果父节点不为空，则
      • (a0, a1) := 节点的计数
      • (b0, b1) := (count[0] - a0, count[1] - a1)
      • 如果 (a0 等于 0 或 a1 等于 0) 且 (b0 等于 0 或 b1 等于 0)，则
        • ans := ans + 1
    • dfs2(节点的左子节点, 节点)
    • dfs2(节点的右子节点, 节点)
  • 在主方法中，执行以下操作：
  • dfs(根节点)
  • ans := 0
  • dfs2(根节点)
  • 返回 ans

让我们来看下面的实现，以便更好地理解：

示例

在线演示

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

更新于：2020年10月20日

138 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告
© . All rights reserved.