Inverser un arbre binaire en Java

Récemment, j'ai commencé à pratiquer quelques exercices LeetCode pour améliorer mes compétences en algorithme/structure de données. Je peux dire que la plateforme offre un bon environnement pour pratiquer et apprendre avec d'autres développeurs des solutions dans plusieurs langages de programmation, discuter, partager des solutions avec d'autres et pratiquer les défis de code demandés par les grandes entreprises.

Qu’est-ce que LeetCode ?

LeetCode est un site Web qui aide les candidats à se préparer aux entretiens de codage. Les utilisateurs peuvent s'entraîner à des défis en utilisant les problèmes de codage et algorithmiques de la plateforme, ainsi que des tests prédéfinis pour la solution du candidat. LeetCode est devenu une ressource populaire pour les entretiens techniques et les concours de codage, aux côtés de HackerRank.

Ma routine pour résoudre des problèmes

Je me fixe pour objectif de résoudre au moins 3 défis par jour, et ma façon de réfléchir à une solution implique mon iPad, un stylet pour écrans et l'application Freeform. J'essaie de dessiner et de réfléchir aux solutions, et cela m'aide beaucoup dans mes soumissions de code. De nombreux défis semblent difficiles à première vue, mais avec quelques minutes de réflexion et d'architecture de la solution (je recommande d'écrire votre processus de réflexion). Si je ne trouve pas la bonne solution en 30 minutes, alors je consulte les soumissions des autres développeurs pour découvrir où sont mes erreurs (parfois une petite étape que j'ai oubliée dans mon code). Même si votre solution est assez bonne, je vous recommande fortement de consulter les soumissions des autres pour réfléchir à d'autres façons de résoudre ce problème (certaines plus ou moins efficaces).

Le problème de l’inversion de l’arbre binaire

Il y a quelques jours, j'ai été confronté au problème Invert Binary Tree chez LeetCode, un défi bien connu demandé lors de certaines interviews et un problème que j'ai vu en suivant un cours de structures de données/algorithmes à l'université. Bien que je n'ai jamais relevé ce défi lors d'un entretien et que je n'ai jamais eu explicitement à inverser un arbre binaire dans mon travail, savoir comment en inverser un m'a donné plus d'expérience avec DS, les arbres et la pensée algorithmique et pratiquer certaines techniques comme la récursivité.
Je vous recommande d'essayer de résoudre ce problème avant de lire la suite de cet article

La solution

Le problème Inverser l'arbre binaire m'a demandé de "Étant donné la racine d'un arbre binaire, inverser l'arbre et renvoyer sa racine." (en d’autres termes, nous devrions « refléter » l’arbre). J'ai utilisé le langage de programmation Java pour soumettre une solution, mais les étapes sont les mêmes pour les autres langages (avec de petites modifications de syntaxe). L'exemple d'entrée et le résultat attendu sont présentés ci-dessous :

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

Nous allons utiliser la technique de récursion pour appeler récursivement la méthode invertTree(), en passant un côté de l'arbre comme racine. Ainsi, comme chaque récursion le demande, nous devons définir une condition d'arrêt où la pile de récursion se terminera et renverra le résultat respectif de l'appel de récursion. Après, nous inversons simplement les côtés de l'arborescence, en attribuant à root.left la valeur renvoyée par la récursion passant root.right comme paramètre, et faisons de même à root.right en attribuant la valeur du résultat de récursion root.left. Comme nous modifions la valeur d'origine, nous avons besoin d'une variable auxiliaire pour stocker le résultat original de root.left (vous avez probablement implémenté un code comme celui-ci à l'université et l'avez appelé méthode swap().

A la fin on renvoie la racine avec les nœuds inversés. Vous pouvez vérifier le code ci-dessous :

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null) {
            return null;
        }

        TreeNode aux = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(aux);

        return root;
    }
}

Gardez à l'esprit qu'il peut exister de nombreuses solutions différentes pour différents problèmes, et c'est génial. Tout le monde a une façon de penser et de programmer, un domaine de structures de données, etc. Vous n'avez pas besoin de suivre exactement le même code pour résoudre ce problème, mais vous devez faire attention à la complexité de l'algorithme (vous pouvez utiliser 3 imbriqués pour résoudre un problème , mais c'est moins performatif que d'utiliser 1 pour).

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!