Compartilhamento de tecnologia

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

A travessia hierárquica de uma árvore refere-se a um método de travessia que visita todos os nós da árvore em ordem hierárquica. As etapas específicas são as seguintes:

1. Começando no nó raiz, enfileire o nó raiz.
2. Faça um loop até que a fila esteja vazia:
   • Retira um nó da fila e o acessa.
   • Enfileirar todos os nós filhos deste nó em sequência.
3. Travessia completa.

Pontos de conhecimento relacionados sobre passagem de nível:

1. Fila: a travessia hierárquica requer o uso de uma fila para armazenar nós temporariamente. Cada vez que um nó é acessado, seus nós filhos são colocados na fila, e o nó principal da fila é retirado para acesso no próximo ciclo.
2. Loop: a passagem de nível requer uma operação de loop até que a fila esteja vazia. Durante o loop, os nós são continuamente adicionados e retirados da fila até que todos os nós sejam percorridos.
3. Acesso ao nó: O acesso ao nó pode ser determinado de acordo com a necessidade, pode ser para imprimir o valor do nó, ou para realizar outras operações.
4. Enfileirando nós filhos: a travessia hierárquica requer o enfileiramento de todos os nós filhos de cada nó para continuar acessando em loops subsequentes.

Ideia:

1. Primeiro, crie uma fila e enfileire o nó raiz.
2. Faça um loop até que a fila esteja vazia:
   • Retira um nó da fila e o acessa.
   • Enfileirar todos os nós filhos deste nó em sequência.
3. Travessia completa.

Essa ideia é a chave para implementar a travessia hierárquica por meio do uso de filas. Cada vez que um nó é retirado da fila e acessado, seus nós filhos são enfileirados, garantindo assim o acesso em ordem hierárquica.

exemplo:

102. Travessia de ordem de nível da árvore binária

Fornece o nó raiz da árvore bináriaroot, retorna seu valor de nópassagem de ordem de nível . (ou seja, visite todos os nós camada por camada, da esquerda para a direita).

Exemplo 1:

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

Exemplo 2:

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

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