【二叉树】删点成林

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​​ 搜索即可~