【二叉树】删点成林

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

---