Technologieaustausch

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Die hierarchische Durchquerung eines Baums bezieht sich auf eine Durchquerungsmethode, die alle Knoten im Baum in hierarchischer Reihenfolge besucht. Die spezifischen Schritte sind wie folgt:

1. Beginnen Sie mit dem Stammknoten und stellen Sie den Stammknoten in die Warteschlange.
2. Schleife, bis die Warteschlange leer ist:
   • Entnimmt einen Knoten aus der Warteschlange und greift darauf zu.
   • Stellen Sie alle untergeordneten Knoten dieses Knotens nacheinander in die Warteschlange.
3. Vollständige Durchquerung.

Verwandte Wissenspunkte zum Leveldurchqueren:

1. Warteschlange: Die hierarchische Durchquerung erfordert die Verwendung einer Warteschlange zum vorübergehenden Speichern von Knoten. Bei jedem Zugriff auf einen Knoten werden dessen untergeordnete Knoten der Reihe nach in die Warteschlange gestellt und der Kopfknoten der Warteschlange wird für den Zugriff im nächsten Zyklus herausgenommen.
2. Schleife: Das Durchlaufen von Ebenen erfordert eine Schleifenoperation, bis die Warteschlange leer ist. Während der Schleife werden kontinuierlich Knoten hinzugefügt und aus der Warteschlange entfernt, bis alle Knoten durchlaufen sind.
3. Knotenzugriff: Der Zugriff auf den Knoten kann je nach Bedarf festgelegt werden. Dies kann darin bestehen, den Wert des Knotens zu drucken oder andere Vorgänge auszuführen.
4. Untergeordnete Knoten in die Warteschlange stellen: Bei der hierarchischen Durchquerung müssen alle untergeordneten Knoten jedes Knotens in die Warteschlange gestellt werden, um in nachfolgenden Schleifen weiterhin darauf zugreifen zu können.

Idee:

1. Erstellen Sie zunächst eine Warteschlange und stellen Sie den Stammknoten in die Warteschlange.
2. Schleife, bis die Warteschlange leer ist:
   • Entnimmt einen Knoten aus der Warteschlange und greift darauf zu.
   • Stellen Sie alle untergeordneten Knoten dieses Knotens nacheinander in die Warteschlange.
3. Vollständige Durchquerung.

Diese Idee ist der Schlüssel zur Implementierung hierarchischer Durchquerung mithilfe von Warteschlangen. Jedes Mal, wenn ein Knoten aus der Warteschlange entfernt und auf ihn zugegriffen wird, werden seine untergeordneten Knoten in die Warteschlange gestellt, wodurch der Zugriff in hierarchischer Reihenfolge sichergestellt wird.

Beispiel:

102. Level-Ordnung-Durchquerung des Binärbaums

Geben Sie den Wurzelknoten des Binärbaums anroot, gibt seinen Knotenwert zurückLevel-Ordnungs-Durchquerung . (d. h. besuchen Sie alle Knoten Schicht für Schicht, von links nach rechts).

Beispiel 1:

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

Beispiel 2:

输入：root = [1]
输出：[[1]]

Beispiel 3:

输入：root = []
输出：[]

// 层序遍历二叉树并返回结果列表
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> lists = new ArrayList<>(); // 用于存储层序遍历结果的列表
    Queue<TreeNode> queue = new LinkedList<>(); // 辅助队列，用于层序遍历
    if (root == null) {
        return new ArrayList<List<Integer>>(); // 如果根节点为空，直接返回空列表
    }
    queue.add(root); // 将根节点加入队列
    while (!queue.isEmpty()) {
        int size = queue.size(); // 当前层的节点数
        List<Integer> list = new ArrayList<>(); // 用于存储当前层节点值的列表
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll(); // 出队列
            list.add(node.val); // 将节点值加入当前层列表
            // 将当前节点的左右子节点加入队列，以便遍历下一层
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        lists.add(list); // 将当前层的节点值列表加入最终结果列表
    }
    return lists; // 返回层序遍历结果列表
}