Berbagi teknologi

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

Penjelajahan hierarki pohon mengacu pada metode penjelajahan yang mengunjungi semua node di pohon dalam urutan hierarki. Langkah-langkah spesifiknya adalah sebagai berikut:

1. Dimulai dari simpul akar, enqueue simpul akar.
2. Ulangi hingga antrian kosong:
   • Mengeluarkan node dari antrian dan mengaksesnya.
   • Enqueue semua node anak dari node ini secara berurutan.
3. Lintasan lengkap.

Poin pengetahuan terkait tentang level traversal:

1. Antrian: Traversal hierarki memerlukan penggunaan antrian untuk menyimpan node sementara. Setiap kali sebuah node diakses, node turunannya dimasukkan ke dalam antrian secara bergantian, dan node utama dari antrian tersebut diambil untuk diakses pada siklus berikutnya.
2. Loop: Level traversal memerlukan operasi loop hingga antrian kosong. Selama perulangan, node terus ditambahkan dan dikeluarkan dari antrean hingga semua node dilintasi.
3. Akses node: Akses ke node dapat ditentukan sesuai kebutuhan, bisa untuk mencetak nilai node, atau untuk melakukan operasi lainnya.
4. Enqueuing node anak: Traversal hierarki memerlukan enqueuing semua node anak dari setiap node agar dapat terus mengakses di loop berikutnya.

Ide:

1. Pertama, buat antrian dan enqueuekan node akar.
2. Ulangi hingga antrian kosong:
   • Mengeluarkan node dari antrian dan mengaksesnya.
   • Enqueue semua node anak dari node ini secara berurutan.
3. Lintasan lengkap.

Ide ini adalah kunci untuk mengimplementasikan traversal hierarki melalui penggunaan antrian. Setiap kali sebuah node di-dequeued dan diakses, node turunannya juga di-enqueued, sehingga memastikan akses dalam urutan hierarki.

contoh:

102. Penjelajahan tingkat-urutan pohon biner

Memberi Anda simpul akar dari pohon binerroot, mengembalikan nilai simpulnyapenjelajahan tingkat-urutan . (yaitu mengunjungi semua node lapis demi lapis, dari kiri ke kanan).

Contoh 1:

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

Contoh 2:

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

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