网站建设公司郑州,手机网站制作软件,阿里巴巴组织调整,深圳宣传片给出二叉树的根节点 root#xff0c;树上每个节点都有一个不同的值。
如果节点值在 to_delete 中出现#xff0c;我们就把该节点从树上删去#xff0c;最后得到一个森林#xff08;一些不相交的树构成的集合#xff09;。
返回森林中的每棵树。你可以按任意顺序组织答案…给出二叉树的根节点 root树上每个节点都有一个不同的值。
如果节点值在 to_delete 中出现我们就把该节点从树上删去最后得到一个森林一些不相交的树构成的集合。
返回森林中的每棵树。你可以按任意顺序组织答案。
示例 1
输入root [1,2,3,4,5,6,7], to_delete [3,5] 输出[[1,2,null,4],[6],[7]] 示例 2
输入root [1,2,4,null,3], to_delete [3] 输出[[1,2,4]]
leetcode链接https://leetcode.cn/problems/delete-nodes-and-return-forest
思路 采用 dfs 的方式来做首先判断 节点是否是根节点如果结点是根节点且不会被删除那么就把该节点就会被添加到结果数组中如果根节点被删除那么其子节点会变成跟节点。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution:def __init__(self):self.res []def delNode(self, root, to_delete_dict, is_root):if root None:return Noneis_del root.val in to_delete_dict### 如果 root 节点被删除, 那么其左右子节点都是根节点root.left self.delNode(root.left, to_delete_dict, is_del)root.right self.delNode(root.right, to_delete_dict, is_del)if is_del:return Noneelse:#### 如果是根节点并且不会删除, 则添加if is_root:self.res.append(root)return rootdef delNodes(self, root: Optional[TreeNode], to_delete: List[int]) - List[TreeNode]:if root None:return []to_delete_dict {}for x in to_delete:to_delete_dict[x] 1temp self.delNode(root, to_delete_dict, True)return self.res