Заполнение следующих правых указателей в каждом узле — Daily JS (День 16)

Постановка задачи
Вам дано совершенное двоичное дерево, в котором все листья находятся на одном уровне, а каждый родитель имеет двух детей. Бинарное дерево имеет следующее определение:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}
Войти в полноэкранный режим Выход из полноэкранного режима

Заполните каждый указатель next, чтобы он указывал на следующий правый узел. Если нет следующего правого узла, то следующий указатель должен быть установлен в NULL.

Первоначально все следующие указатели устанавливаются в NULL.

Примеры
Пример 1:

Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.
Вход в полноэкранный режим Выход из полноэкранного режима

Пример 2:

Input: root = []
Output: []
Войти в полноэкранный режим Выход из полноэкранного режима

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

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106
Войти в полноэкранный режим Выйти из полноэкранного режима

Решение

const connect = (root) => {
    if(!root) return root;
    let q = [root];

    while(q.length){
        const temp = [];
        for(let i = 0; i < q.length; i++){
            const n = q[i];

            n.next = q[i+1] || null;
            if(n.left){
                temp.push(n.left);
                temp.push(n.right);
            }
        }
        q = temp;
    }

    return root;
};
Войти в полноэкранный режим Выйти из полноэкранного режима

Проблема с LeetCode:
https://leetcode.com/problems/populating-next-right-pointers-in-each-node/

Надеюсь, вы будете регулярно получать обновления.
Спасибо, увидимся в следующем посте.

Оставьте комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *