Comment reconstruire un arbre binaire en Java

Question : Entrez les résultats du parcours en pré-ordre et du parcours en ordre d'un arbre binaire, veuillez reconstruire l'arbre binaire. On suppose que les résultats du parcours de pré-ordre d'entrée et du parcours dans l'ordre ne contiennent pas de nombres répétés. Par exemple, si vous saisissez la séquence de parcours en pré-ordre {1,2,4,7,3,5,6,8} et la séquence de parcours en ordre {4,7,2,1,5,3,8 ,6}, puis reconstruisez l'arbre binaire et revenez.

Analyse de la solution :

1. Déterminez le nœud racine en fonction du parcours de pré-commande du premier nœud.

2. Recherchez le nœud racine dans le parcours dans l'ordre et déterminez la longueur du sous-arbre gauche et la longueur du sous-arbre droit.

3. En fonction de la longueur, prenez le parcours de pré-ordre du sous-arbre gauche et le parcours de pré-ordre du sous-arbre droit dans le parcours de pré-ordre, et prenez le parcours de pré-ordre du sous-arbre gauche et le parcours de pré-ordre du sous-arbre droit dans le parcours d'ordre inférieur. >

4. Récurisez le sous-arbre gauche et le sous-arbre droit, et attribuez le nœud racine du sous-arbre gauche et le nœud racine du sous-arbre droit au nœud racine.

Tutoriels vidéo gratuits recommandés :

Apprentissage Java

Code :

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.*;
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(pre.length == 0 || in.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(pre[0]);
        for(int i = 0 ; i < in.length; i++) {
            if(in[i] == pre[0]) {
                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i));
                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length)
                ,Arrays.copyOfRange(in,i+1,in.length));
            }
        }
        return root;
    }
}

Tutoriels recommandés pour des articles plus connexes :

Introduction à la programmation Java

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!