前言

之前一直做得题目是在一棵树上捯饬，今天做一道把二叉树变为森林的题目，多点捯饬的空间。

题目

//给出二叉树的根节点 root，树上每个节点都有一个不同的值。 
//
// 如果节点值在 to_delete 中出现，我们就把该节点从树上删去，最后得到一个森林（一些不相交的树构成的集合）。 
//
// 返回森林中的每棵树。你可以按任意顺序组织答案。 
//
// 
//
// 示例： 
//
// 
//
// 输入：root = [1,2,3,4,5,6,7], to_delete = [3,5]
//输出：[[1,2,null,4],[6],[7]]
// 
//
// 
//
// 提示： 
//
// 
// 树中的节点数最大为 1000。 
// 每个节点都有一个介于 1 到 1000 之间的值，且各不相同。 
// to_delete.length <= 1000 
// to_delete 包含一些从 1 到 1000、各不相同的值。

题目拆解

这道题目简单来看和二叉搜索树的删除节点有点像，但是这里面不需要替换节点，节点删掉就直接砍断，斩断情丝，斩断牵挂。

但是不需要替换节点，其实也没有变得简单，因为分为两段以后，还要继续找被删除的节点，所以，最终可能也想蚯蚓一样，切成很多段...为啥今天总是要用奇怪的比喻。

好，那继续拆解这个题目，由上述可知，二叉树被切分的关键点在于是否找到了和待删除目标值相同的节点，找到了，就从这个地方一分为二，并且把父节点指向当前节点的指针清空。所以我们定义一个节点的两个状态

1节点被删除了
2 节点还在

在dfs遍历的时候，将这种状态告诉父节点，然后让父节点吧对应的指针清除掉。
如果节点还在，那就直接处理子节点，然后把当前节点返回即可。

代码一阶段

class Solution {

    Set<Integer> deleteMap = new HashSet<>();
    List<TreeNode> res = new ArrayList<>();

    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
        for (int i : to_delete) {
            deleteMap.add(i);
        }

        TreeNode dummyNode= new TreeNode(-1);
        dummyNode.left = root;
        int rootRes = delNodes(root,dummyNode,true);
        if (rootRes == 2) {
            res.add(dummyNode.left);
        }
        return res;

    }

    int delNodes(TreeNode node, TreeNode parent, boolean isLeft) {
        // 返回状态
        // 1 节点没了
        // 2 还有货
        // 如果为空,代表状态1,节点没了
        if (node == null) return 1;
        // 如果是待删除节点,删除后节点也没了
        if (deleteMap.contains(node.val)) {
            // 把父节点指向自己的链接删掉
            if (isLeft) parent.left = null;
            if (!isLeft) parent.right = null;
            // 将不为空的子树,插入结果集
            int leftRes = delNodes(node.left, node, true);
            if (leftRes == 2) res.add(node.left);
            node.left = null;
            int rightRes = delNodes(node.right, node, false);
            if (rightRes == 2) res.add(node.right);
            node.right = null;
            return 1;
        } else {
            // 如果子树为空,将指针清除
            int leftRes = delNodes(node.left, node, true);
            if (leftRes == 1) {
                node.left = null;
            }
            int rightRes = delNodes(node.right, node, false);
            if (rightRes == 1) {
                node.right = null;
            }

            return 2;
        }
    }
}

第一版的代码写的还是有很多繁琐的地方，比如在递归时候引入的变量很多，还要给root节点设置一个哑结点，还有很多状态的判断，实际上，因为只有两种状态，所以只需要根据dfs返回的节点是否为null来判断即可，多余的父节点其实可以通过返回结果让父节点直接处理就可以了，不需要当前节点来做多余的事情，所以，我们来到了

代码二阶段

class Solution {

    Set<Integer> deleteMap = new HashSet<>();
    List<TreeNode> res = new ArrayList<>();

    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
        for (int i : to_delete) {
            deleteMap.add(i);
        }


        root = delNodes(root);
        if (root != null) {
            res.add(root);
        }
        return res;


    }
    
    TreeNode delNodes(TreeNode node) {

        // 如果节点为null, 返回null
        if (node == null) return null;
        // 如果当前节点的值和是需要删除的节点,将左右子树中,不为空的插入结果集
        if (deleteMap.contains(node.val)) {
            TreeNode left = delNodes(node.left);
            if (left != null) res.add(node.left);
            TreeNode right = delNodes(node.right);
            if (right != null) res.add(node.right);
            return null;
        } else {
            // 如果当前节点不是待删除节点,处理子树,同时返回当前节点
            node.left = delNodes(node.left);
            node.right = delNodes(node.right);
            return node;
        }
    }
}