Задача: 971. Flip Binary Tree To Match Preorder Traversal
Сложность: medium

Дано корневое дерево с n узлами, где каждому узлу уникально присвоено значение от 1 до n. Также дана последовательность из n значений voyage, которая является желаемым обходом дерева в порядке pre-order.

Любой узел в бинарном дереве можно перевернуть, поменяв местами его левое и правое поддеревья. Например, переворот узла 1 будет иметь следующий эффект:

Переверните минимальное количество узлов, чтобы обход дерева в порядке pre-order соответствовал voyage.

Верните список значений всех перевернутых узлов. Вы можете вернуть ответ в любом порядке. Если невозможно перевернуть узлы в дереве, чтобы сделать обход в порядке pre-order соответствующим voyage, верните список [-1].

Пример:

Input: root = [1,2], voyage = [2,1]
Output: [-1]
Explanation: It is impossible to flip the nodes such that the pre-order traversal matches voyage.

👨‍💻 Алгоритм:

1⃣Выполните поиск в глубину. Если в каком-либо узле значение узла не соответствует значению в voyage, верните [-1].

2⃣Иначе определите, когда нужно перевернуть: если следующее ожидаемое число в voyage (voyage[i]) отличается от следующего потомка.

3⃣Переверните узел, добавьте его значение в список перевернутых узлов и продолжите обход дерева, пока весь порядок обхода pre-order не будет соответствовать voyage.

😎 Решение:

class Solution {
    public $flipped;
    public $index;
    public $voyage;

    function flipMatchVoyage($root, $voyage) {
        $this->flipped = [];
        $this->index = 0;
        $this->voyage = $voyage;

        $this->dfs($root);
        if (!empty($this->flipped) && $this->flipped[0] == -1) {
            return [-1];
        }

        return $this->flipped;
    }

    function dfs($node) {
        if ($node !== null) {
            if ($node->val != $this->voyage[$this->index++]) {
                $this->flipped = [-1];
                return;
            }

            if ($this->index < count($this->voyage) && $node->left !== null && $node->left->val != $this->voyage[$this->index]) {
                $this->flipped[] = $node->val;
                $this->dfs($node->right);
                $this->dfs($node->left);
            } else {
                $this->dfs($node->left);
                $this->dfs($node->right);
            }
        }
    }
}

Ставь 👍 и забирай 📚 Базу знаний