Бинарное дерево: вид справа

Источник: https://leetcode.com/problems/binary-tree-right-side-view/

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

Пример 1:

Дано: root = [1,2,3,null,5,null,4]
Результат: [1,3,4]

Пример 2:

Дано: root = [1,null,3]
Результат: [1,3]

Пример 3:

Дано: root = []
Результат: []
 

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

• Количество узлов в дереве:[0, 100].
• -100 <= Node.val <= 100


Идея решения

Мы будем обходить дерево в порядке BFS, то есть по "этажам". Элемента "этажа" будем записывать так, чтобы самый правыйэлемент шел первым. Его будем записывать и в результат, а остальные элементы этажа нам нужны, чтобы подсчитать следующий "этаж".

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

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList(); //   результат запишем сюда
        Queue<TreeNode> queue = new LinkedList();
        if (root == null) return result;
        
        queue.offer(root); // корень находится на самом верхнем этаже
        while (queue.size() != 0) { // пока этаж существует
            int size = queue.size(); // сколько элементов на этаже
            for (int i=0; i<size; i++) {
                TreeNode cur = queue.poll();
                if (i == 0) result.add(cur.val); // первый элемент этажа и есть
// самый правый->результат

// строим следющий этаж, добавляем в очередь
                if (cur.right != null) queue.offer(cur.right); //  сначала правый
                if (cur.left != null) queue.offer(cur.left); //  потом левый
            }
            
        }
        return result;
    }
}