Обмен технологиями

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

Иерархический обход дерева — это метод обхода, который посещает все узлы дерева в иерархическом порядке. Конкретные шаги заключаются в следующем:

1. Начиная с корневого узла, поставьте корневой узел в очередь.
2. Цикл, пока очередь не станет пустой:
   • Извлекает узел из очереди и получает к нему доступ.
   • Поставьте в очередь все дочерние узлы этого узла.
3. Полный обход.

Сопутствующие сведения о прохождении уровней:

1. Очередь: иерархический обход требует использования очереди для временного хранения узлов. Каждый раз при обращении к узлу его дочерние узлы по очереди помещаются в очередь, а головной узел очереди извлекается для доступа в следующем цикле.
2. Цикл: обход уровня требует операции цикла, пока очередь не станет пустой. Во время цикла узлы постоянно добавляются и удаляются из очереди, пока не будут пройдены все узлы.
3. Доступ к узлу: доступ к узлу может быть определен в соответствии с потребностями, это может быть печать значения узла или выполнение других операций.
4. Постановка в очередь дочерних узлов. Иерархический обход требует постановки в очередь всех дочерних узлов каждого узла, чтобы продолжить доступ в последующих циклах.

Идея:

1. Сначала создайте очередь и поставьте в нее корневой узел.
2. Цикл, пока очередь не станет пустой:
   • Извлекает узел из очереди и получает к нему доступ.
   • Поставьте в очередь все дочерние узлы этого узла.
3. Полный обход.

Эта идея является ключом к реализации иерархического обхода с помощью очередей. Каждый раз, когда узел выводится из очереди и осуществляется доступ, его дочерние узлы ставятся в очередь, обеспечивая таким образом доступ в иерархическом порядке.

пример:

102. Поуровневый обход двоичного дерева.

Дайте вам корневой узел двоичного дереваroot, возвращает значение своего узлаобход по уровням . (т.е. посетить все узлы слой за слоем, слева направо).

Пример 1:

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

Пример 2:

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

Пример 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; // 返回层序遍历结果列表
}