Κοινή χρήση τεχνολογίας

한어Русский язык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; // 返回层序遍历结果列表
}