0x00 题目
给出二叉树的根节点 root
树上每个节点都有一个不同的值
如果节点值在 to_delete
中出现
我们就把该节点从树上删去
最后得到一个森林(一些不相交的树构成的集合)
返回森林中的每棵树
你可以按任意顺序组织答案
0x01 思路
某个节点需要删除
时
需要判断它的左右
节点是否为空
不为空则添加
到结果数组中
然后返回一个空节点
(nil) 给上层
上层直接替换即可
所以,按照这个思路
使用后序
遍历方式即可
0x02 解法
语言:Swift
树节点:TreeNode
public class TreeNode {
public var val: Int
public var left: TreeNode?
public var right: TreeNode?
public init() { self.val = 0; self.left = nil; self.right = nil; }
public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
self.val = val
self.left = left
self.right = right
}
}
解法:
func delNodes(_ root: TreeNode?, _ to_delete: [Int]) -> [TreeNode?] {
var res: [TreeNode?] = []
func del(_ root: TreeNode?, _ to_delete: [Int]) -> TreeNode? {
guard let root = root else { return nil }
// 分别去左右子树进行删除操作
let left = del(root.left, to_delete)
let right = del(root.right, to_delete)
// 更新左右子树
root.left = left
root.right = right
// 节点需要删除
if to_delete.contains(root.val) {
if left != nil {
res.append(left)
}
if right != nil {
res.append(right)
}
return nil
}
return root
}
// 根节点是否需要删除?
let r = del(root, to_delete)
if r != nil {
res.append(r)
}
return res
}
0x03 我的小作品
欢迎体验我的作品之一:小编辑器-XCompiler
在线编辑器,包含多种语言
App Store
搜索即可~