技術共有

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