n叉树的层序遍历

发表于 更新于 分类于

算法-n叉树的层序遍历

背景

  • 算法–n叉树的层序遍历

  • 博主以代码随想录算法公开课进行学习

题目

  • 给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

    树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

    示例 1：

    1
    2
    输入：root = [1,null,3,2,4,null,5,6]
    输出：[[1],[3,2,4],[5,6]]

    示例 2:

    1
    2
    输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
    输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

思路

  • 与层序遍历一致

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

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

        que.offerLast(root);

        while(!que.isEmpty()){
            int levelSize = que.size();
            //存储当前层的节点值
            List<Integer> levelList = new ArrayList<>();

            for(int i = 0;i < levelSize; i++){
                Node poll = que.pollFirst();
                levelList.add(poll.val);
                List<Node> children = poll.children;
                if(children == null || children.size() == 0){
                    continue;
                }
                //子节点非空则依次入队
                for(Node child : children){
                    if(child != null){
                        //防止单个节点为null
                        que.offerLast(child);
                    }
                }
            }
            list.add(levelList);
        }
        return list;
    } 
   
}

总结

  • N 叉树层序遍历的核心是队列 + 分层遍历：用队列存储节点，通过 levelSize 控制每层的遍历范围。
  • 边界处理：必须判断根节点为空的情况，以及子节点为空的情况，避免空指针异常。