Задача: 199. Binary Tree Right Side View
Сложность: medium

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

Пример:

Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]

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

1⃣Инициализируйте список правого обзора rightside. Инициализируйте две очереди: одну для текущего уровня и одну для следующего. Добавьте корень в очередь nextLevel.

2⃣Пока очередь nextLevel не пуста:
Инициализируйте текущий уровень: currLevel = nextLevel и очистите очередь следующего уровня nextLevel.
Пока очередь текущего уровня не пуста:
Извлеките узел из очереди текущего уровня.
Добавьте сначала левый, а затем правый дочерний узел в очередь nextLevel.
Теперь очередь currLevel пуста, и узел, который у нас есть, является последним и составляет часть правого обзора. Добавьте его в rightside.

3⃣Верните rightside.

😎 Решение:

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        if (root == null) return new ArrayList<Integer>();

        ArrayDeque<TreeNode> nextLevel = new ArrayDeque() {
            {
                offer(root);
            }
        };
        ArrayDeque<TreeNode> currLevel = new ArrayDeque();
        List<Integer> rightside = new ArrayList();

        TreeNode node = null;
        while (!nextLevel.isEmpty()) {
            currLevel = nextLevel;
            nextLevel = new ArrayDeque<>();

            while (!currLevel.isEmpty()) {
                node = currLevel.poll();

                if (node.left != null) nextLevel.offer(node.left);
                if (node.right != null) nextLevel.offer(node.right);
            }

            if (currLevel.isEmpty()) rightside.add(node.val);
        }
        return rightside;
    }
}

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