Учитывая дерево, начальный лист и конечный лист, разделите его на 3 части

Question

Я делаю некоторые DOM-манипуляции с текстовыми элементами (текстовый узел, p, span, b, i и т. Д.), Где проблема может быть сформулирована следующим образом:

При заданном дереве началолист и конечный лист, разделите это дерево на 3 части:

• одна часть состоит из всего, что находится слева от начального узла
• одна часть состоит из всего, что находится между начальным узлом иконечный узел (включительно)
• одна часть состоит из всего, что находится справа от конечного узла

Обратите внимание, что здесь левый и правый относится к обходу предварительного заказа по дереву.

Узлы на дереве могут дублироваться для разделения при необходимости

Так, например, если у меня есть следующее дерево:

где J - начальный лист, а G - конечный лист, тогда после разбиения результат будет следующим:

Как я могудостичь этого?Я знаю, что это, вероятно, потребует обхода слева направо с использованием обхода предварительного заказа / DFS, но я не уверен, как построить новые поддеревья.

Answer 1

Создать индекс предварительного заказа.Это таблица поиска от Node до ее позиции в обходе предварительного заказа.

Напишите функцию cloneWithFilter, которая принимает узел и предикат и возвращает клонированный узел или null.Идея состоит в том, что узел должен быть включен, если он проходит фильтр или если какой-либо из его дочерних элементов проходит фильтр.Псевдокод выглядит следующим образом:

Node? cloneWithFilter(Node node, Predicate<Node> filter) {
    val newNode = new Node(node.value);
    newNode.children = node.children.map(c -> cloneWithFilter(c, filter))
                                    .filter(c -> c != null);
    return filter(node) || !newNode.children.empty() : newNode : null;
}

Вы можете использовать это для создания деталей, просто используйте различные фильтры.Например, для средней части вы можете написать:

cloneWithFilter(root, node -> preOrderIndex[node] >= preOrderIndex[from] && preOrderIndex[node] <= preOrderIndex[to] )