1110. 删点成林

LC每日一题，参考1110. 删点成林。

题目

给出二叉树的根节点 root，树上每个节点都有一个不同的值。
如果节点值在 to_delete 中出现，我们就把该节点从树上删去，最后得到一个森林（一些不相交的树构成的集合）。

返回森林中的每棵树。你可以按任意顺序组织答案。

输入：root = [1,2,3,4,5,6,7], to_delete = [3,5]
输出：[[1,2,null,4],[6],[7]]
输入：root = [1,2,4,null,3], to_delete = [3]
输出：[[1,2,4]]

解题思路

• 深度优先搜索：因为要删除节点,优先考虑使用dfs。

深度优先搜索

class Solution {
    List<TreeNode> ans;
    boolean[] hash = new boolean[1001];
    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
        //树用根节点表示 删除节点后有子节点则成为新树
        ans = new ArrayList<>();
        //先用哈希表存储待删除节点值
        for(int i : to_delete) hash[i] = true;
        //由于要删除节点 考虑使用dfs
        dfs(null,root,null);
        return ans;
    }
    void dfs(TreeNode node,TreeNode left,TreeNode right) {
        if(left != null) {
            if(hash[left.val]) {
                if(node != null) node.left = null;
                dfs(null,left.left,left.right);
            }
            else {
                if(node == null)ans.add(left);
                dfs(left,left.left,left.right);
            }
        }
        if(right != null) {
            if(hash[right.val]) {
                if(node != null) node.right = null;
                dfs(null,right.left,right.right);
            }
            else {
                if(node == null) ans.add(right);
                dfs(right,right.left,right.right);
            }
        }
    }
}

复杂度分析

• 时间复杂度：O(n)，n为树的节点数,总共会访问每个节点一次。
• 空间复杂度：O(m)，哈希表使用空间,m为要删除的节点数。