用 Python 删除节点并返回森林

pythonserver side programmingprogramming更新于 2025/8/25 13:32:17

假设我们有一个二叉树的根,树中的每个节点都有一个唯一的值。删除所有在 to_delete 中有值的节点后,我们剩下一片森林。我们必须在剩余的森林中找到树的根。因此,如果输入如下

如果 to_delete 数组为 [3,5],则输出为

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

  • 定义一个数组 res
  • 定义一个方法solve(),它将采用节点、to_delete 数组和一个布尔类型信息,用于指示节点是否为根节点。该方法将如下所示 −
  • 如果节点为空,则返回空节点
  • 如果节点的值在 to_delete 数组中,则 flag := true
  • 如果 flag 为 false 且 is_root 为 true,则将节点插入 res
  • 节点左侧 := resolve(节点左侧、to_delete、flag)
  • 节点右侧 := resolve(节点右侧、to_delete、flag)
  • 设置 flag 时返回 none,否则返回 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]]

相关文章


有用资源