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.