Compartir tecnología

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

El recorrido jerárquico de un árbol se refiere a un método de recorrido que visita todos los nodos del árbol en orden jerárquico. Los pasos específicos son los siguientes:

1. Comenzando desde el nodo raíz, ponga en cola el nodo raíz.
2. Repita hasta que la cola esté vacía:
   • Saca un nodo de la cola y accede a él.
   • Ponga en cola todos los nodos secundarios de este nodo en secuencia.
3. Recorrido completo.

Puntos de conocimiento relacionados sobre el recorrido de niveles:

1. Cola: el recorrido jerárquico requiere el uso de una cola para almacenar temporalmente nodos. Cada vez que se accede a un nodo, sus nodos secundarios se colocan en la cola por turno y el nodo principal de la cola se retira para acceder en el siguiente ciclo.
2. Bucle: el recorrido de nivel requiere una operación de bucle hasta que la cola esté vacía. Durante el ciclo, los nodos se agregan y retiran de la cola continuamente hasta que se atraviesan todos los nodos.
3. Acceso al nodo: El acceso al nodo se puede determinar según las necesidades, puede ser para imprimir el valor del nodo o para realizar otras operaciones.
4. Poner en cola los nodos secundarios: el recorrido jerárquico requiere poner en cola todos los nodos secundarios de cada nodo para poder continuar accediendo en bucles posteriores.

Idea:

1. Primero, cree una cola y ponga en cola el nodo raíz.
2. Repita hasta que la cola esté vacía:
   • Saca un nodo de la cola y accede a él.
   • Ponga en cola todos los nodos secundarios de este nodo en secuencia.
3. Recorrido completo.

Esta idea es la clave para implementar el recorrido jerárquico mediante el uso de colas. Cada vez que se retira de la cola un nodo y se accede a él, sus nodos secundarios se ponen en cola, lo que garantiza el acceso en orden jerárquico.

ejemplo:

102. Recorrido de orden de nivel del árbol binario

Darte el nodo raíz del árbol binario.root, devuelve su valor de nodorecorrido de orden de nivel . (es decir, visitar todos los nodos capa por capa, de izquierda a derecha).

Ejemplo 1:

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

Ejemplo 2:

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

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