1. Transformation d'un arbre binaire en liste chaînée

L'objectif est d'aplatir un arbre binaire pour qu'il ressemble à une liste chaînée simple, en utilisant la même structure TreeNode. La liste doit suivre l'ordre d'un parcours en pré-ordre (racine, gauche, droite), avec tous les nœuds gauches mis à null.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private TreeNode dernierVisite = null;

    public void flatten(TreeNode root) {
        if (root == null) return;
        
        // Parcours post-ordre inversé pour reconstruire la liste
        flatten(root.right);
        flatten(root.left);
        
        root.right = dernierVisite;
        root.left = null;
        dernierVisite = root;
    }
}

Approche : On utilise une récursion qui traite d'abord le sous-arbre droit, puis le gauche. En maintenant un pointeur sur le dernier nœud traité, on peut lier chaque nœud actuel au reste de la "liste" déjà formée.

2. Vérification de la somme d'un chemin (Path Sum)

On cherche à déterminer s'il existe un chemin allant de la racine à une feuille dont la somme des valeurs des nœuds est égale à targetSum.

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;
        
        // Si c'est une feuille, on vérifie la valeur restante
        if (root.left == null && root.right == null) {
            return targetSum == root.val;
        }
        
        int reste = targetSum - root.val;
        return hasPathSum(root.left, reste) || hasPathSum(root.right, reste);
    }
}

Aprpoche : Une simple récursion soustrayant la valeur du nœud courant de la cible. Si l'on atteint une feuille avec une valeur égale au reste de la somme, le chemin est valide.

3. Somme des nombres formés par les chemins racine-feuille

Chaque chemin de la racine à une feuille représente un nombre. Par exemple, le chemin 1 -> 2 -> 3 représente 123. Il faut calculer la somme totale de tous ces nombres.

class Solution {
    public int sumNumbers(TreeNode root) {
        return calculerSomme(root, 0);
    }

    private int calculerSomme(TreeNode node, int valeurActuelle) {
        if (node == null) return 0;
        
        int nouvelleValeur = valeurActuelle * 10 + node.val;
        
        if (node.left == null && node.right == null) {
            return nouvelleValeur;
        }
        
        return calculerSomme(node.left, nouvelleValeur) + 
               calculerSomme(node.right, nouvelleValeur);
    }
}

4. Somme de chemin maximale dans un arbre binaire

Un chemin peut commencer et se terminer sur n'importe quel nœud. La contrainte est que chaque nœud ne peut être utilisé qu'une seule fois dans la séquence.

class Solution {
    private int maxGlobal = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        explorer(root);
        return maxGlobal;
    }

    private int explorer(TreeNode node) {
        if (node == null) return 0;

        // On ignore les contributions négatives
        int gainGauche = Math.max(explorer(node.left), 0);
        int gainDroit = Math.max(explorer(node.right), 0);

        // Prix du chemin passant par ce nœud comme sommet
        int prixCheminActuel = node.val + gainGauche + gainDroit;
        maxGlobal = Math.max(maxGlobal, prixCheminActuel);

        // Retourne le gain maximal d'une branche unique
        return node.val + Math.max(gainGauche, gainDroit);
    }
}

5. Itérateur pour Arbre de Recherche Binaire (BST)

L'itérateur doit retourner les éléments dans l'ordre croissant (parcours infixe) avec une complexité spatiale optimisée.

import java.util.Stack;

class BSTIterator {
    private Stack<TreeNode> pile = new Stack<>();

    public BSTIterator(TreeNode root) {
        pousserGauche(root);
    }
    
    public int next() {
        TreeNode node = pile.pop();
        if (node.right != null) {
            pousserGauche(node.right);
        }
        return node.val;
    }
    
    public boolean hasNext() {
        return !pile.isEmpty();
    }

    private void pousserGauche(TreeNode node) {
        while (node != null) {
            pile.push(node);
            node = node.left;
        }
    }
}

Optimisation : Au lieu de stocker tous les nœuds dans une liste, on utilise une pile pour simuler la récursion, ce qui réduit l'espace mémoire à O(h), où h est la hauteur de l'arbre.

6. Compter les nœuds d'un arbre binaire complet

Dans un arbre complet, toutes les couches sont remplies sauf éventuellement la dernière. On peut utliiser cette propriété pour opitmiser le calcul, bien qu'une solution récursive simple soit souvent acceptable.

class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
}

7. Ancêtre commun le plus proche (LCA)

Trouver le nœud le plus bas dans l'arbre qui possède à la fois p et q comme descendants.

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // Base case: si on trouve l'un des nœuds ou une feuille
        if (root == null || root == p || root == q) {
            return root;
        }

        TreeNode gauche = lowestCommonAncestor(root.left, p, q);
        TreeNode droite = lowestCommonAncestor(root.right, p, q);

        // Si p et q sont trouvés dans des branches différentes, root est le LCA
        if (gauche != null && droite != null) {
            return root;
        }

        return (gauche != null) ? gauche : droite;
    }
}

Approche : On explore l'arbre de manière récursive. Si un nœud reçoit des retours non nuls de ses deux sous-arbres, il est l'ancêtre commun recherché.