Konstruiere eine BST aus der Ebenenreihenfolge (BFS-Reihenfolge)

Question

Ich habe versucht, eine BST aus einer bestimmten Reihenfolge (BFS-Reihenfolge) zu erstellen. Ich weiß, dass es möglich ist, aber ich weiß nicht, wie ich das schreiben kann. Das Problem ist, dass ich mit der BFS-Sequenz arbeiten musste. Also kann ich Rekursion hier nicht verwenden und ich musste mein Programm iterativ schreiben ... Und ich finde das ein wenig verwirrend.

Ich habe versucht, dies zu tun:

public static TreeNode constructBFSTree(ArrayList<Integer> bfs) { 
    if (bfs== null) return null; 
    ArrayList<TreeNode> result = new ArrayList<TreeNode>(); 
     for (int i = 0; i < bfs.size()-1; i ++){ 
      TreeNode node = result.get(i); 
      int leftValue = (bfs.get(i+1)!=null)? bfs.get(i+1) : Integer.MAX_VALUE ; 
      int rightValue = (bfs.get(i+2)!=null)? bfs.get(i+2) : Integer.MIN_VALUE; 

      node.left = (leftValue <= node.data)? new TreeNode(leftValue) : null; 
      node.right = (rightValue > node.data)? new TreeNode(rightValue) : null; 
      result.add(node); 
     } 

     return result.get(0); 
    } 

Die lokale Arraylist hier nicht wirklich wichtig ist. Ich füge es einfach hinzu, um den ersten Knoten zu fangen, der die Wurzel des konstruierten Baums ist, den ich zurückgeben soll. Das Problem ist, dass ich nur die Wurzel und ihr Kind bekomme.

Wie kann ich dieses Programm schreiben?

Answer 1

Wie wäre es, wenn Sie den folgenden Code ausprobieren? (Hinweis: Ich habe es nicht getestet, da Sie die Klassendefinitionen nicht angegeben haben. Aber es sollte Sie in die richtige Richtung schieben.)

Was ich über die TreeNode Klasse vermute, ist, dass ihr Konstruktor eine Ganzzahl und das nimmt Es initialisiert die left und right Zeiger auf null. Zum Beispiel:

class TreeNode { 
    TreeNode left; 
    TreeNode right; 
    int key; 
    public TreeNode(int key) { 
     this.key = key; 
     this.left = null; 
     this.right = null; 
    } 
} 

Der Code für die Funktion dann könnte wie folgt aussehen:

public static TreeNode constructBFSTree(ArrayList<Integer> bfs) { 
    if (bfs == null || bfs.isEmpty()) { 
     return null; 
    } 

    Queue<TreeNode> q = new Queue<TreeNode>(); 
    TreeNode root = new TreeNode(bfs.get(0)); 
    q.add(root); 
    int i = 1; 
    while (!q.isEmpty() && i < bfs.size()) { 
     TreeNode currentNode = q.poll(); 
     currentNode.left = new TreeNode(bfs.get(i++)); 
     q.add(curentNode.left); 
     if (i < bfs.length()) { 
      currentNode.right = new TreeNode(bfs.get(i++)); 
      q.add(currentNode.right); 
     } 
    } 
    return root; 
}