Élagage d'un arbre binaire de recherche

L'objectif est de modifier un arbre binaire de recherche (ABR) pour que toutes les valeurs de ses nœuds se situent dans un intervalle donné [minVal, maxVal]. La structure relative des nœuds conservés doit rester intacte. Grâce aux propriétés fondamentales des ABR, nous pouvons optimiser cette opération en évitant de parcourir l'intégralité de l'arbre.

Approche récursive

Si la valeur du nœud actuel est inférieure à minVal, cela signifie que son sous-arbre gauche contient également des valeurs invalides. Nous pouvons donc ignorer la gauche et ne conserver que le résultat de l'élagage de son sous-arbre droit. Inversement, si la valeur est supérieure à maxVal, nous ne conservons que le sous-arbre gauche élagué. Si la valeur est dans l'intervalle, nous élaguons récursivement les deux sous-arbres.

class Solution {
public:
    TreeNode* trimBST(TreeNode* node, int minVal, int maxVal) {
        if (!node) return nullptr;
        
        if (node->val < minVal) {
            return trimBST(node->right, minVal, maxVal);
        }
        if (node->val > maxVal) {
            return trimBST(node->left, minVal, maxVal);
        }
        
        node->left = trimBST(node->left, minVal, maxVal);
        node->right = trimBST(node->right, minVal, maxVal);
        
        return node;
    }
};

Approche itérative

Pour une solution itérative, nous devons d'abord ajuster la racine pour qu'elle se trouve dans l'intervalle valide. Ensuite, nous parcourons l'arbre pour corriger les sous-arbres gauches dont les valeurs sont trop petites, et les sous-arbres droits dont les valeurs sont trop grandes, en réaffectant les pointeurs appropriés.

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int minBound, int maxBound) {
        if (!root) return nullptr;
        
        while (root && (root->val < minBound || root->val > maxBound)) {
            if (root->val < minBound) root = root->right;
            else root = root->left;
        }
        
        TreeNode* current = root;
        while (current) {
            while (current->left && current->left->val < minBound) {
                current->left = current->left->right;
            }
            current = current->left;
        }
        
        current = root;
        while (current) {
            while (current->right && current->right->val > maxBound) {
                current->right = current->right->left;
            }
            current = current->right;
        }
        
        return root;
    }
};

Conversion d'un tableau trié en arbre binaire de recherche équilibré

Étant donné un tableau d'entires trié par ordre croissant, le but est de le transformer en un ABR strictement équilibré en hauteur. Un arbre est considéré comme équilibré si la différence de hauteur entre les sous-arbres gauche et droit de chaque nœud ne dépasse pas 1.

Approche récursive

La propriété d'un ABR stipule qu'un parcours infixe produit une séquence triée. Par conséquent, pour garantir l'équilibre, nous sélectionnons l'élément central du tableau comme racine. Les éléments à gauche forment le sous-arbre gauche, et ceux à droite forment le sous-arbre droit. Ce processus de division est appliqué récursivement.

class Solution {
public:
    TreeNode* sortedArrayToBST(const vector<int>& values) {
        return constructBST(values, 0, values.size() - 1);
    }
    
private:
    TreeNode* constructBST(const vector<int>& values, int startIdx, int endIdx) {
        if (startIdx > endIdx) return nullptr;
        
        int middleIdx = startIdx + (endIdx - startIdx) / 2;
        TreeNode* subRoot = new TreeNode(values[middleIdx]);
        
        subRoot->left = constructBST(values, startIdx, middleIdx - 1);
        subRoot->right = constructBST(values, middleIdx + 1, endIdx);
        
        return subRoot;
    }
};

Approche itérative

L'implémentation itérative simule la récursion en utilisant des files d'attente. Une file stocke les nœuds à traiter, tandis que deux autres files maintiennent les indices de début et de fin des sous-tableaux correspondants.

class Solution {
public:
    TreeNode* sortedArrayToBST(const vector<int>& values) {
        if (values.empty()) return nullptr;
        
        TreeNode* mainRoot = new TreeNode(0);
        queue<TreeNode*> nodes;
        queue<int> leftBounds;
        queue<int> rightBounds;
        
        nodes.push(mainRoot);
        leftBounds.push(0);
        rightBounds.push(values.size() - 1);
        
        while (!nodes.empty()) {
            TreeNode* activeNode = nodes.front(); nodes.pop();
            int lBound = leftBounds.front(); leftBounds.pop();
            int rBound = rightBounds.front(); rightBounds.pop();
            
            int mid = lBound + (rBound - lBound) / 2;
            activeNode->val = values[mid];
            
            if (lBound <= mid - 1) {
                activeNode->left = new TreeNode(0);
                nodes.push(activeNode->left);
                leftBounds.push(lBound);
                rightBounds.push(mid - 1);
            }
            
            if (rBound >= mid + 1) {
                activeNode->right = new TreeNode(0);
                nodes.push(activeNode->right);
                leftBounds.push(mid + 1);
                rightBounds.push(rBound);
            }
        }
        return mainRoot;
    }
};

Transformation d'un arbre binaire de recherche en arbre de sommes cumulées

Cette opération consiste à modifier chaque nœud d'un ABR de sorte que sa nouvelle valeur soit égale à la somme de sa valeur initiale et de toutes les valeurs des nœuds qui lui sont strictement supérieurs dans l'arbre.

Approche récursive

Un parcours infixe standard (gauche-milieu-droite) visite les nœuds d'un ABR dans l'ordre croissant. Pour accumuler les valeurs supérieures, nous inversons ce parcours en utilisant un ordre droite-milieu-gauche. Cela nous permet de traiter les nœuds du plus grand au plus petit, en maintenant une somme courante que nous ajoutons à chaque nœud visité.

class Solution {
private:
    int accumulatedSum = 0;
    
    void reverseInOrder(TreeNode* node) {
        if (!node) return;
        reverseInOrder(node->right);
        
        accumulatedSum += node->val;
        node->val = accumulatedSum;
        
        reverseInOrder(node->left);
    }
    
public:
    TreeNode* convertBST(TreeNode* root) {
        accumulatedSum = 0;
        reverseInOrder(root);
        return root;
    }
};

Approche itérative

La logique itérative reproduit le parcours infixe inversé à l'aide d'une pile. Nous poussons continuellement les nœuds droits sur la pile jusqu'à atteindre l'extrémité droite de l'arbre, puis nous traitons les nœuds en les dépilant et en mettant à jour la somme cumulative avant de passer aux sous-arbres gauches.

class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        int runningTotal = 0;
        stack<TreeNode*> nodeStack;
        TreeNode* navigator = root;
        
        while (navigator || !nodeStack.empty()) {
            while (navigator) {
                nodeStack.push(navigator);
                navigator = navigator->right;
            }
            
            navigator = nodeStack.top();
            nodeStack.pop();
            
            runningTotal += navigator->val;
            navigator->val = runningTotal;
            
            navigator = navigator->left;
        }
        
        return root;
    }
};