Condivisione della tecnologia

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

L'attraversamento gerarchico di un albero si riferisce a un metodo di attraversamento che visita tutti i nodi dell'albero in ordine gerarchico. I passaggi specifici sono i seguenti:

1. Partendo dal nodo radice, accodare il nodo radice.
2. Ciclo finché la coda non è vuota:
   • Estrae un nodo dalla coda e vi accede.
   • Accoda tutti i nodi figlio di questo nodo in sequenza.
3. Attraversamento completo.

Punti di conoscenza correlati sull'attraversamento del livello:

1. Coda: l'attraversamento gerarchico richiede l'uso di una coda per archiviare temporaneamente i nodi. Ogni volta che si accede a un nodo, i suoi nodi figli vengono messi in coda a turno e il nodo principale della coda viene escluso per l'accesso nel ciclo successivo.
2. Ciclo: l'attraversamento del livello richiede un'operazione di ciclo finché la coda non è vuota. Durante il ciclo, i nodi vengono continuamente aggiunti e rimossi dalla coda finché tutti i nodi non vengono attraversati.
3. Accesso al nodo: L'accesso al nodo può essere determinato in base alle esigenze, può essere quello di stampare il valore del nodo, oppure di eseguire altre operazioni.
4. Accodamento dei nodi figli: l'attraversamento gerarchico richiede l'accodamento di tutti i nodi figli di ciascun nodo per continuare ad accedere nei cicli successivi.

Idea:

1. Innanzitutto, crea una coda e accoda il nodo root.
2. Ciclo finché la coda non è vuota:
   • Estrae un nodo dalla coda e vi accede.
   • Accoda tutti i nodi figlio di questo nodo in sequenza.
3. Attraversamento completo.

Questa idea è la chiave per implementare l'attraversamento gerarchico attraverso l'uso delle code. Ogni volta che un nodo viene rimosso dalla coda e vi si accede, i suoi nodi figli vengono accodati, garantendo così l'accesso in ordine gerarchico.

esempio:

102. Attraversamento dell'ordine dei livelli di un albero binario

Fornisci il nodo radice dell'albero binarioroot, restituisce il valore del nodoattraversamento dell'ordine dei livelli . (ovvero visita tutti i nodi strato per strato, da sinistra a destra).

Esempio 1:

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

Esempio 2:

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

Esempio 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; // 返回层序遍历结果列表
}