用 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]]
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/

