LeetCode 429. N 叉树的层序遍历

Categories:

题目描述
思路分析
1. 解法一：广度优先搜索（推荐）
相似题目

题目描述

✅ 429. N 叉树的层序遍历

思路分析

解法一：广度优先搜索（推荐）

核心思路：

用队列按层遍历，每一轮固定处理当前队列长度的节点。

将当前层节点值收集后，依次把子节点入队。

直到队列为空结束。

复杂度分析：

时间复杂度：O(n)，其中 n 表示节点数量。

空间复杂度：O(n)，其中 n 表示队列在最宽层的节点数。

import java.util.*;

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        Deque<Node> queue = new ArrayDeque<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>();

            for (int i = 0; i < size; i++) {
                Node node = queue.poll();
                level.add(node.val);

                // 将当前节点的子节点入队
                if (node.children != null) {
                    for (Node child : node.children) {
                        if (child != null) {
                            queue.offer(child);
                        }
                    }
                }
            }

            res.add(level);
        }

        return res;
    }
}

func levelOrder(root *Node) [][]int {
	if root == nil {
		return [][]int{}
	}

	res := make([][]int, 0)
	queue := []*Node{root}

	for len(queue) > 0 {
		size := len(queue)
		level := make([]int, 0, size)

		for i := 0; i < size; i++ {
			node := queue[0]
			queue = queue[1:]
			level = append(level, node.Val)

			// 将当前节点的子节点入队
			for _, child := range node.Children {
				if child != nil {
					queue = append(queue, child)
				}
			}
		}

		res = append(res, level)
	}

	return res
}

相似题目

题目	难度	考察点
102. 二叉树的层序遍历	中等	BFS、层序遍历
103. 二叉树的锯齿形层序遍历	中等	BFS、层序遍历
107. 二叉树的层序遍历 II	中等	BFS、层序遍历
637. 二叉树的层平均值	简单	BFS、层统计
559. N 叉树的最大深度	简单	BFS/DFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/99753440