Задача: 103. Binary Tree Zigzag Level Order Traversal
Сложность: medium

Дан корень бинарного дерева. Верните обход узлов дерева по уровням в виде зигзага (то есть слева направо, затем справа налево для следующего уровня и чередуйте далее).

Пример:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]

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

1⃣Мы также можем реализовать поиск в ширину (BFS) с использованием одного цикла. Трюк заключается в том, что мы добавляем узлы для посещения в очередь, а узлы разных уровней разделяем с помощью какого-то разделителя (например, пустого узла). Разделитель отмечает конец уровня, а также начало нового уровня.

2⃣Здесь мы принимаем второй подход, описанный выше. Можно начать с обычного алгоритма BFS, к которому мы добавляем элемент порядка зигзага с помощью deque (двусторонней очереди).

3⃣Для каждого уровня мы начинаем с пустого контейнера deque, который будет содержать все значения данного уровня. В зависимости от порядка каждого уровня, т.е. либо слева направо, либо справа налево, мы решаем, с какого конца deque добавлять новый элемент.

😎 Решение:

class TreeNode {
    public $val;
    public $left;
    public $right;

    public function __construct($val, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

class Solution {
    function zigzagLevelOrder($root) {
        $result = [];
        if ($root === null) {
            return $result;
        }

        $nodeQueue = new SplQueue();
        $nodeQueue->enqueue($root);
        $nodeQueue->enqueue(null);
        $isOrderLeft = true;
        $levelList = [];

        while (!$nodeQueue->isEmpty()) {
            $currentNode = $nodeQueue->dequeue();

            if ($currentNode !== null) {
                if ($isOrderLeft) {
                    $levelList[] = $currentNode->val;
                } else {
                    array_unshift($levelList, $currentNode->val);
                }

                if ($currentNode->left !== null) {
                    $nodeQueue->enqueue($currentNode->left);
                }
                if ($currentNode->right !== null) {
                    $nodeQueue->enqueue($currentNode->right);
                }
            } else {
                $result[] = $levelList;
                $levelList = [];
                if (!$nodeQueue->isEmpty()) {
                    $nodeQueue->enqueue(null);
                }
                $isOrderLeft = !$isOrderLeft;
            }
        }

        return $result;
    }
}

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