1110. Delete Nodes And Return Forest

leetcode medium

#array#csharp#hash-table#leetcode#linked-list#medium#recursion#search#tree#two-pointers

Task

Дан корень бинарного дерева, каждый узел в дереве имеет уникальное значение.

После удаления всех узлов со значением из to_delete, остаётся лес (несвязное объединение деревьев).

Верните корни деревьев в оставшемся лесу. Вы можете вернуть результат в любом порядке.

Пример:

Input: root = [1,2,3,4,5,6,7], to_delete = [3,5]

Output: [[1,2,null,4],[6],[7]]

C# solution

matched/original

public class Solution {
    public IList<TreeNode> DelNodes(TreeNode root, int[] to_delete) {
        var toDeleteSet = new HashSet<int>(to_delete);
        var forest = new List<TreeNode>();
        root = ProcessNode(root, toDeleteSet, forest);
        if (root != null) {
            forest.Add(root);
        }
        return forest;
    }
    private TreeNode ProcessNode(TreeNode node, HashSet<int> toDeleteSet, List<TreeNode> forest) {
        if (node == null) {
            return null;
        }
        node.left = ProcessNode(node.left, toDeleteSet, forest);
        node.right = ProcessNode(node.right, toDeleteSet, forest);
        if (toDeleteSet.Contains(node.val)) {
            if (node.left != null) {
                forest.Add(node.left);
            }
            if (node.right != null) {
                forest.Add(node.right);
            }
            return null;
        }
        return node;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public IList<TreeNode> DelNodes(TreeNode root, vector<int>& to_delete) {
        var toDeleteSet = new HashSet<int>(to_delete);
        var forest = new List<TreeNode>();
        root = ProcessNode(root, toDeleteSet, forest);
        if (root != null) {
            forest.push_back(root);
        }
        return forest;
    }
    private TreeNode ProcessNode(TreeNode node, HashSet<int> toDeleteSet, List<TreeNode> forest) {
        if (node == null) {
            return null;
        }
        node.left = ProcessNode(node.left, toDeleteSet, forest);
        node.right = ProcessNode(node.right, toDeleteSet, forest);
        if (toDeleteSet.Contains(node.val)) {
            if (node.left != null) {
                forest.push_back(node.left);
            }
            if (node.right != null) {
                forest.push_back(node.right);
            }
            return null;
        }
        return node;
    }
}

Java solution

auto-draft, review before submit

import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    public List<TreeNode> DelNodes(TreeNode root, int[] to_delete) {
        var toDeleteSet = new HashSet<int>(to_delete);
        var forest = new List<TreeNode>();
        root = ProcessNode(root, toDeleteSet, forest);
        if (root != null) {
            forest.add(root);
        }
        return forest;
    }
    private TreeNode ProcessNode(TreeNode node, HashSet<int> toDeleteSet, List<TreeNode> forest) {
        if (node == null) {
            return null;
        }
        node.left = ProcessNode(node.left, toDeleteSet, forest);
        node.right = ProcessNode(node.right, toDeleteSet, forest);
        if (toDeleteSet.Contains(node.val)) {
            if (node.left != null) {
                forest.add(node.left);
            }
            if (node.right != null) {
                forest.add(node.right);
            }
            return null;
        }
        return node;
    }
}

JavaScript solution

matched/original

var delNodes = function(root, to_delete) {
    const toDeleteSet = new Set(to_delete);
    const forest = [];

    const processNode = (node) => {
        if (!node) return null;

        node.left = processNode(node.left);
        node.right = processNode(node.right);

        if (toDeleteSet.has(node.val)) {
            if (node.left) forest.push(node.left);
            if (node.right) forest.push(node.right);
            return null;
        }
        return node;
    };

    root = processNode(root);
    if (root) {
        forest.push(root);
    }

    return forest;
};

Python solution

matched/original

class Solution:
    def delNodes(self, root: TreeNode, to_delete: List[int]) -> List[TreeNode]:
        to_delete_set = set(to_delete)
        forest = []

        def process_node(node):
            if not node:
                return None

            node.left = process_node(node.left)
            node.right = process_node(node.right)

            if node.val in to_delete_set:
                if node.left:
                    forest.append(node.left)
                if node.right:
                    forest.append(node.right)
                return None
            return node

        root = process_node(root)
        if root:
            forest.append(root)

        return forest

Go solution

matched/original

func delNodes(root *TreeNode, to_delete []int) []*TreeNode {
    toDeleteSet := make(map[int]struct{})
    for _, val := range to_delete {
        toDeleteSet[val] = struct{}{}
    }

    var forest []*TreeNode

    var processNode func(*TreeNode) *TreeNode
    processNode = func(node *TreeNode) *TreeNode {
        if node == nil {
            return nil
        }

        node.Left = processNode(node.Left)
        node.Right = processNode(node.Right)

        if _, exists := toDeleteSet[node.Val]; exists {
            if node.Left != nil {
                forest = append(forest, node.Left)
            }
            if node.Right != nil {
                forest = append(forest, node.Right)
            }
            return nil
        }
        return node
    }

    root = processNode(root)
    if root != nil {
        forest = append(forest, root)
    }

    return forest
}

Explanation

Algorithm

Инициализация:

Преобразуйте массив to_delete в множество toDeleteSet для эффективного поиска.

Создайте пустой список forest для хранения корней деревьев в результирующем лесу.

Рекурсивный обход:

Выполните обход дерева в порядке пост-ордера, чтобы сначала обработать все дочерние узлы перед текущим узлом (node):

- рекурсивно вызовите processNode для левого и правого дочерних узлов node и обновите левого и правого дочернего узла с возвращаемым значением.

Оценка узла:

Проверьте, нужно ли удалить текущий узел, проверив, существует ли его значение в toDeleteSet. Если узел нужно удалить:

- если у узла есть левый или правый дочерний узел, добавьте их в forest.

- верните null для его родителя, чтобы эффективно удалить текущий узел, не подключая его обратно к родительскому узлу.

Если узел не нужно удалять, верните сам узел.

😎