So rekonstruieren Sie einen Binärbaum in Java

Frage: Geben Sie die Ergebnisse der Durchquerung vor der Bestellung und der Durchquerung in der Reihenfolge eines Binärbaums ein. Bitte rekonstruieren Sie den Binärbaum. Gehen Sie davon aus, dass die Ergebnisse der eingegebenen Durchquerung vor der Bestellung und der Durchquerung in der Reihenfolge keine wiederholten Zahlen enthalten. Wenn Sie beispielsweise die Durchlaufsequenz vor der Reihenfolge {1,2,4,7,3,5,6,8} und die Durchlaufsequenz in der Reihenfolge {4,7,2,1,5,3,8} eingeben ,6}, rekonstruieren Sie dann den Binärbaum und kehren Sie zurück.

Lösungsanalyse:

1. Bestimmen Sie den Wurzelknoten basierend auf der Vorbestellungsdurchquerung des ersten Knotens.

2. Finden Sie den Wurzelknoten im In-Order-Traversal und bestimmen Sie die Länge des linken Teilbaums und die Länge des rechten Teilbaums.

3. Nehmen Sie entsprechend der Länge die Vorbestellungsdurchquerung des linken Teilbaums und die Vorbestellungsdurchquerung des rechten Teilbaums und die Inorder-Durchquerung des linken Teilbaums und die Inorder-Durchquerung des rechten Teilbaums

4. Rekursieren Sie den linken Teilbaum und den rechten Teilbaum und weisen Sie dem Wurzelknoten den linken Teilbaum-Wurzelknoten und den rechten Teilbaum-Wurzelknoten zu.

Empfohlene kostenlose Video-Tutorials: Java-Lernen

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;
    }
}

Empfohlene Tutorials für weitere verwandte Artikel: Einführung in die Java-Programmierung

Das obige ist der detaillierte Inhalt vonSo rekonstruieren Sie einen Binärbaum in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!