Учитывая root бинарного дерева, представьте, что вы стоите на правой стороне от него, верните значения видимых узлов, упорядоченные сверху вниз.
Пример 1:
Input: root = [1,2,3,null,5,null,4] Output: [1,3,4]
Решение:
В данной задаче нам нужно найти правильный вид бинарного дерева.
Правый вид означает узел, который мы увидим, если посмотрим на дерево с правой стороны.
Во-первых, мы проверим, является ли дерево null или нет.
if(!root)
return ;
Мы создадим переменную h, которая будет текущим уровнем узла. Будет создана еще одна переменная, maxh, для обозначения максимального уровня, достигнутого в любой заданный момент времени.
Мы проверим, превышает ли текущий уровень максимальный уровень. Если да, то он будет виден с правой стороны дерева.
Как только мы получим узел, который присутствует с правой стороны, мы поместим этот узел в вектор ans.
if(h > maxh){
ans.push_back(root -> val);
maxh = h;
}
Следующим шагом является посещение правой стороны для правого представления двоичного дерева, а затем левой стороны.
traverse(root -> right, h + 1, maxh, ans); traverse(root -> left, h + 1, maxh, ans);
Теперь в заданной функции проверьте, является ли дерево нулевым. Если да, то вернуть пустой вектор.
if(!root)
return {};
Корневое значение будет помещено в вектор, и будет вызвана функция перемещения.
ans.push_back(root -> val); traverse(root, 0, maxh, ans);
Последний шаг — вернуть вектор ans.
return ans;
Ниже приведена полная реализация задачи:
Спасибо за прочтение!
S.
