Partage de technologie

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

Le parcours hiérarchique d'un arbre fait référence à une méthode de parcours qui visite tous les nœuds de l'arborescence dans l'ordre hiérarchique. Les étapes spécifiques sont les suivantes :

1. En partant du nœud racine, mettez le nœud racine en file d’attente.
2. Bouclez jusqu'à ce que la file d'attente soit vide :
   • Extrait un nœud de la file d'attente et y accède.
   • Mettez en file d'attente tous les nœuds enfants de ce nœud dans l'ordre.
3. Traversée complète.

Points de connaissances connexes sur la traversée de niveau :

1. File d'attente : le parcours hiérarchique nécessite l'utilisation d'une file d'attente pour stocker temporairement les nœuds. Chaque fois qu'un nœud est accédé, ses nœuds enfants sont placés à leur tour dans la file d'attente et le nœud principal de la file d'attente est retiré pour pouvoir accéder au cycle suivant.
2. Boucle : le parcours de niveau nécessite une opération de boucle jusqu'à ce que la file d'attente soit vide. Pendant la boucle, les nœuds sont continuellement ajoutés et retirés de la file d'attente jusqu'à ce que tous les nœuds soient traversés.
3. Accès au nœud : L'accès au nœud peut être déterminé en fonction des besoins, il peut s'agir d'imprimer la valeur du nœud, ou d'effectuer d'autres opérations.
4. Mise en file d'attente des nœuds enfants : le parcours hiérarchique nécessite la mise en file d'attente de tous les nœuds enfants de chaque nœud afin de continuer à accéder dans les boucles suivantes.

Idée:

1. Tout d’abord, créez une file d’attente et mettez le nœud racine en file d’attente.
2. Bouclez jusqu'à ce que la file d'attente soit vide :
   • Extrait un nœud de la file d'attente et y accède.
   • Mettez en file d'attente tous les nœuds enfants de ce nœud dans l'ordre.
3. Traversée complète.

Cette idée est la clé de la mise en œuvre du parcours hiérarchique grâce à l'utilisation de files d'attente. Chaque fois qu'un nœud est retiré de la file d'attente et accessible, ses nœuds enfants sont mis en file d'attente, garantissant ainsi l'accès dans l'ordre hiérarchique.

exemple:

102. Parcours par ordre de niveau de l'arbre binaire

Donnez-vous le nœud racine de l'arbre binaireroot, renvoie sa valeur de nœudparcours par ordre de niveau . (c'est-à-dire visitez tous les nœuds couche par couche, de gauche à droite).

Exemple 1:

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

Exemple 2 :

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

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