Maison >Java >javaDidacticiel >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 : 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!