Задача: 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 {
    func rightSideView(_ root: TreeNode?) -> [Int] {
        guard let root = root else { return [] }
        
        var nextLevel: [TreeNode] = [root]
        var currLevel: [TreeNode] = []
        var rightside: [Int] = []
        
        while !nextLevel.isEmpty {
            currLevel = nextLevel
            nextLevel = []
            
            for node in currLevel {
                if let left = node.left {
                    nextLevel.append(left)
                }
                if let right = node.right {
                    nextLevel.append(right)
                }
            }
            
            if !currLevel.isEmpty {
                rightside.append(currLevel.last!.val)
            }
        }
        return rightside
    }
}

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