Teknologian jakaminen

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

Puun hierarkkinen läpikulku viittaa läpikulkumenetelmään, joka vierailee puun kaikissa solmuissa hierarkkisessa järjestyksessä. Tarkat vaiheet ovat seuraavat:

1. Aloita juurisolmusta, aseta juurisolmu jonoon.
2. Kierrä, kunnes jono on tyhjä:
   • Nostaa solmun jonosta ja käyttää sitä.
   • Jonoa kaikki tämän solmun lapsisolmut järjestyksessä.
3. Täydellinen läpikulku.

Aiheeseen liittyviä tietopisteitä tason läpikulkusta:

1. Jono: Hierarkkinen läpikulku edellyttää jonon käyttöä solmujen väliaikaiseen tallentamiseen. Joka kerta kun solmua käytetään, sen alisolmut asetetaan jonoon vuorotellen, ja jonon pääsolmu poistetaan pääsyä varten seuraavassa jaksossa.
2. Silmukka: Tason läpikulku vaatii silmukan, kunnes jono on tyhjä. Silmukan aikana solmuja lisätään jatkuvasti ja poistetaan jonosta, kunnes kaikki solmut on kuljetettu.
3. Solmun käyttöoikeus: Pääsy solmuun voidaan määrittää tarpeiden mukaan, se voi olla solmun arvon tulostaminen tai muiden toimintojen suorittaminen.
4. Alisolmujen jonottaminen: Hierarkkinen läpikulku edellyttää jokaisen solmun kaikkien lapsisolmujen jonoamista, jotta pääsyä voidaan jatkaa seuraavissa silmukoissa.

Idea:

1. Luo ensin jono ja aseta juurisolmu jonoon.
2. Kierrä, kunnes jono on tyhjä:
   • Nostaa solmun jonosta ja käyttää sitä.
   • Jonoa kaikki tämän solmun lapsisolmut järjestyksessä.
3. Täydellinen läpikulku.

Tämä idea on avain hierarkkisen läpikulun toteuttamiseen jonoja käyttämällä. Joka kerta kun solmu poistetaan jonosta ja sitä käytetään, sen alisolmut asetetaan jonoon, mikä varmistaa pääsyn hierarkkisessa järjestyksessä.

esimerkki:

102. Binääripuun tasojärjestyksen läpikulku

Anna sinulle binääripuun juurisolmuroot, palauttaa sen solmuarvontasojärjestyksen läpikulku . (eli vieraile kaikissa solmuissa kerros kerrokselta, vasemmalta oikealle).

Esimerkki 1:

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

Esimerkki 2:

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

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