Задача: 897. Increasing Order Search Tree
Сложность: easy

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

Пример:

Input: root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

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

1⃣Выполнить обход дерева в порядке in-order, чтобы получить список узлов.

2⃣Перестроить дерево, устанавливая каждый узел из списка как правый дочерний элемент предыдущего узла и устанавливая левые дочерние элементы в null.

3⃣Вернуть новый корень дерева (первый элемент списка).

😎 Решение:

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode* increasingBST(TreeNode* root) {
        vector<TreeNode*> nodes;
        
        inorder(root, nodes);
        
        for (int i = 0; i < nodes.size() - 1; ++i) {
            nodes[i]->left = nullptr;
            nodes[i]->right = nodes[i + 1];
        }
        
        nodes.back()->left = nullptr;
        nodes.back()->right = nullptr;
        return nodes.front();
    }
    
    void inorder(TreeNode* node, vector<TreeNode*>& nodes) {
        if (node == nullptr) return;
        inorder(node->left, nodes);
        nodes.push_back(node);
        inorder(node->right, nodes);
    }
};

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