Задача: 426. Convert Binary Search Tree to Sorted Doubly Linked List
Сложность: medium

Преобразуйте двоичное дерево поиска в отсортированный кольцевой двусвязный список на месте.

Вы можете считать, что указатели "влево" и "вправо" аналогичны указателям на предшественника и последователя в двусвязном списке. Для кольцевого двусвязного списка предшественник первого элемента является последним элементом, а последователь последнего элемента является первым элементом.

Мы хотим выполнить преобразование на месте. После преобразования левый указатель узла дерева должен указывать на его предшественника, а правый указатель должен указывать на его последователя. Вы должны вернуть указатель на самый маленький элемент списка.

Пример:

Input: root = [4,2,5,1,3]
Output: [1,2,3,4,5]
Explanation: The figure below shows the transformed BST. The solid line indicates the successor relationship, while the dashed line means the predecessor relationship.

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

1⃣Инициализируйте первые и последние узлы как null.

2⃣Вызовите стандартную вспомогательную рекурсивную функцию helper(root):
Если узел не равен null:
Вызовите рекурсию для левого поддерева helper(node.left).
Если последний узел не равен null, свяжите последний узел и текущий узел.
Иначе инициализируйте первый узел.
Пометьте текущий узел как последний: last = node.
Вызовите рекурсию для правого поддерева helper(node.right).

3⃣Свяжите первые и последние узлы, чтобы замкнуть кольцевой двусвязный список, затем верните первый узел.

😎 Решение:

class Node {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    constructor() {
        this.first = null;
        this.last = null;
    }

    helper(node) {
        if (node !== null) {
            this.helper(node.left);

            if (this.last !== null) {
                this.last.right = node;
                node.left = this.last;
            } else {
                this.first = node;
            }
            this.last = node;

            this.helper(node.right);
        }
    }

    treeToDoublyList(root) {
        if (root === null) return null;

        this.helper(root);

        this.last.right = this.first;
        this.first.left = this.last;
        return this.first;
    }
}

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