Python 中刪除節點並返回森林

假設我們有一棵二叉樹的根節點，樹中的每個節點都有一個唯一的值。刪除所有值為 `to_delete` 中的值的節點後，剩下的節點構成一個森林。我們需要找到這個森林中每棵樹的根節點。

如果 `to_delete` 陣列為 [3,5]，則輸出為：

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

  • 定義一個數組 `res`
  • 定義一個方法 `solve()`，它將接收節點、`to_delete` 陣列和一個布林型別的 `info` 引數（表示該節點是否是根節點）。該方法的工作方式如下：
  • 如果節點為空，則返回 null
  • 如果節點的值在 `to_delete` 陣列中，則 `flag := true`
  • 如果 `flag` 為 false 且 `is_root` 為 true，則將節點插入 `res`
  • 節點的左子節點 := `solve(節點的左子節點, to_delete, flag)`
  • 節點的右子節點 := `solve(節點的右子節點, to_delete, flag)`
  • 如果設定了 `flag`，則返回 null；否則返回 false
  • 在主方法中呼叫 `solve()` 方法，例如 `solve(node, to_delete, true)`

讓我們來看下面的實現，以便更好地理解：

示例

class Solution(object):
   def delNodes(self, root, to_delete):
      """
      :type root: TreeNode
      :type to_delete: List[int]
      :rtype: List[TreeNode]
      """
      to_delete = set(to_delete)
      self.res = []
      self.solve(root,to_delete,True)
      return self.res
   def solve(self,node,to_delete,is_root):
      if not node:
         return None
      flag = node.val in to_delete
      if not flag and is_root:
         self.res.append(node)
      node.left = self.solve(node.left,to_delete,flag)
      node.right = self.solve(node.right,to_delete,flag)
      return None if flag else node

輸入

[1,2,3,4,5,6,7]
[3,5]

輸出

[[1,2,null,4],[6],[7]]

更新於：2020年3月5日

187 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告