preface

We’ve been working on a tree together. Today we’re going to turn a binary tree into a forest. There’s more room for us to work together.

The title

Delete some forest

// Give the root node of the binary tree, root, each node in the tree has a different value. // // If the node value appears in to_delete, we delete the node from the tree and end up with a forest (a collection of disjoint trees). // // Return to each tree in the forest. You can organize your answers in any order. / / / / / / / / example: / / / / / / / / input: root =,2,3,4,5,6,7 [1], to_delete = (3, 5) / / output: [[1, 2, null, 4], [6], [7]] / / / / / / / / / / tip: The maximum number of nodes in the // // // tree is 1000. // Each node has a value between 1 and 1000, which varies from node to node. To_delete. Length <= 1000 // To_delete contains a number of different values from 1 to 1000.Copy the code

The title and dismantling

This topic simply looks like the binary search tree to delete the node, but there is no need to replace the node, node deleted directly cut off, cut off the affection, cut off the care.

But there is no need to replace the node, in fact, it is not easy, because after divided into two sections, but also continue to look for the deleted node, so, may eventually like earthworms, cut into many sections… Why do we always use weird metaphors today.

It can be seen from the above that the key point of binary tree segmentation is whether the node with the same value as the target to be deleted is found. If it is found, the node is divided into two parts and the pointer pointing to the current node is cleared. So we define two states of a node

  • 1 Node is deleted
  • Two nodes are still there

During DFS traversal, this state is told to the parent node, and then the parent node clears the corresponding pointer. If the node is still there, process the child node directly and return the current node.

Code Stage 1

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;
        }
    }
}
Copy the code

In the first version of the code, there are still many tedious places, such as introducing a lot of variables in recursion, setting a dummy node for the root node, and judging a lot of states. In fact, because there are only two states, we only need to determine whether the node returned by DFS is null. The redundant parent node can actually be returned to the parent node directly to process, do not need the current node to do extra work, so here we are

Code Stage 2

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) {// If the node is null, return null if (node == null) return null; If (deleteMap. Contains (node.val)) {TreeNode left = delNodes(node.left); TreeNode left = delNodes(node. if (left ! = null) res.add(node.left); TreeNode right = delNodes(node.right); if (right ! = null) res.add(node.right); return null; } else {// If the current node is not the node to be deleted, process the subtree and return the current node node.left = delNodes(node.left); node.right = delNodes(node.right); return node; }}}Copy the code

conclusion

Above is local parsing and antithesis, today a little harvest is to guarantee a code bugfree can process a bit, as much as possible to ensure more coverage, such as a stage of the code, in fact, the parent node pointer to child nodes of the empty processing some redundant, but writing is more intuitive and reliable, so in the second stage optimization, The focus is on how to optimize the logic to make the code look cleaner.

The two-phase code actually takes about the same time to execute, although it does look cleaner.

This article is participating in the “Nuggets 2021 Spring recruiting campaign. Click here to view