Развернуть поддеревья, чтобы получить заданный обход

Источник: https://leetcode.com/problems/flip-binary-tree-to-match-preorder-traversal/

Дань кореньroot двоичного дерева с n вершинами, где значение каждой вершины уникально в интервале от 1 до n. Дана также последовательность voyage из n элементов, которая обозначает желаемый прямой (pre-order: root, left, right) обход дерева.

Каждая вершина в исходном дереве может быть развернута, то есть его левое поддерево становится правым, а правое - левым. Например, разворот вершины 1 дает такой эффект:

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

Вернуть список развернутых вершин (их порядок в ответе не имеет значения). Если невозможно никакими разворотами получитьvoyage, вернуть список в единственным элементом[-1].

Пример 1:

Дано: root = [1,2], voyage = [2,1]
Результат: [-1]
Пояснение: Невозможно никак развернуть это дерево, чтобы получить искомую последовательность. Прямой обход подразумевает, что первым элементом в результате обхода всегда будет 1 (root).

Пример 2:

 

Дано: root = [1,2,3], voyage = [1,3,2]
Результат: [1]
Пояснение: Разворот 1 означает, что 2 и 3 поменяются местами. И тогда прямой обход дерева будет совпадать с искомой последовательностью.

Пример 3:

Дано: root = [1,2,3], voyage = [1,2,3]
Результат: []
Пояснение: Исходное дерево уже таково, что его прямой обход совпадает с искомой последовательностью. Решение существует, но оно пустое.

Огранияения:

• Число вершин в дереве n.
• n == voyage.length
• 1 <= n <= 100
• 1 <= Node.val, voyage[i] <= n
• Все значения в вершних уникальны
  
• Все значения в искомой последовательности voyage уникальны.

Идея решения

Идея решения

Попробуем выводить результат обхода дерева, одновременно сканируя массив voyage. Для сканирования бужем использовать индекс i. Изначально корень дерева должен иметь значение равное первому элементу искомой последовательности (в индексе 0). Если это не так, то невозможно сделать разворота так, чтобы получить искомую последовательность.

Значение в узле левого поддерева должно совпадать с элементом в индексе 1. Если это не так, то мы поставим правое поддерево на место левого, а левое - на место праваого. Если и в этом случае значение (нового левого) узла не совпадает со сканируемым элементом, то решения не существует. Если же левый узел соответвтует сканируемому элементу, то мы рекурсивно повторяем рассуждения для левого поддерва.

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

Будем использовать DFS, который состоит из 3 шагов:

1. проверить конечность углубления (DFS = поиск в глубину);
2. если можно углубляться, то делаем шаг углубления, получаем результат;
3. на основании результата выносим вердикт.

Что делать, если какая-то вершина не будет совпадать с элементом в индексе сканирования?

Имплементация

class Solution {
    List<Integer> res = new ArrayList<>(); // сюда выводим результат разворотов
    int i = 0; // индекс элемента в искомой последовательности

    public List<Integer> flipMatchVoyage(TreeNode root, int[] v) {
        return dfs(root, v) ? res // если решение существует, то оно в ответе res
            : Arrays.asList(-1); // иначе возвращаем список с единственным элементом -1
    }

    public Boolean dfs(TreeNode node, int[] v) {
// шаг 1: проверка завершения рекурсии
        if (node == null) return true; // мы достигли листьев дерева и ни разу не встретили аномалии
// шаг 2: шаг рекурсии
        if (node.val != v[i++]) return false; // в текущей вершине аномалия:
// ее значение не совпадает с ожидаемым элементом поэтому возвращаем false;
// если же аномалии нет, то мы увеличиваем индекс i в сканировании последовательности v

// текущий элемент искомой последовательности должен совпадать с левым узлом
        if (node.left != null && node.left.val != v[i]) {
// если это не так, то мы пытаемся развернуть текущий узел node
            res.add(node.val); // добавляем его в результат res
            return dfs(node.right, v) && dfs(node.left, v); // углубляемся в левое и правое поддерево, поменям их порядок рассмотрения (сначала рассматриваем right, потом left)
        }
// если же левый узел совпадает с рассматриваем элементом v[i], то мы углубляемся
// без разворота (сначала рассматриваем left, потом right)
        return dfs(node.left, v) && dfs(node.right, v);

// шаг 3: сборка результатов углубления не нужна
    }
}