【算法题解】45. N叉树的层序遍历

ゝ一纸荒年。 2024-03-17 12:05 31阅读 0赞

> 这是一道 **中等难度** 的题  
>   
> https://leetcode.cn/problems/n-ary-tree-level-order-traversal/

### 题目 ###

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

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

**示例 1：**  
![3c874b1c65debcc42b05ed76957094fd.png][]

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

**示例 2：**  
![1e6a6e109bf6048e467e305402f3959c.png][]

输入：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]
    ]

**提示：**

*  树的高度不会超过  1000 1000 1000
 *  树的节点总数在  \[ 0 , 1 0 4 \] \[0, 10^4\] \[0,104\] 之间

--------------------

### 题解 ###

树的层序遍历有一个固定的解题思路：

*使用队列，一层一层的入队，然后再一层一层的按照入队顺序出队。*

首先入队的是根结点，然后根节点出队，记录答案后将其子节点从左到右依次入队。

然后子节点再依次出队，出队时依然是记录答案后再将出队了的这个节点的子节点依次入队，就这样一层一层走下去。直到队列为空的时候，即遍历完成。

**需要注意的是：**题目要求每一层返回一个数组，所以我们需要知道每一层的节点个数（假如为 `count` ），那么取完 `count` 个节点后，再取就是下一层的节点了，就需要新开一个数组记录了。

以题目给定的示例一为例。  
![5be39abc2e4cbd9de66ce34c477b5f45.png][]

第二层节点是 `3`，`2`，`4`；共 `3` 个，所以取完这 `3` 个节点后，剩下的就是第三层了。  
![354f6f3d7e93ef4e1dc933fb7b13cc99.png][]

![15768ed2aa5282864cc8cc1a5896a2dc.png][]

以 **Java** 代码为例：

while(!queue.isEmpty()){
        
        // 当前层的节点数
        int count = queue.size();
    
        // 当前这层入队的节点全部出队
        for(int i = 0; i < count; i++){
        
            // TODO 1.当前这层入队的节点一个一个的出队
            // TODO 2.记录答案
            // TODO 3.子节点依次入对列
        }
    }

当队列不空的时候就一直循环取值，即外层 `while` 循环。

计算当前层有多少个节点，记为 `count` 。然后依次将这 `count` 个节点取出来，即内层 `for` 循环，这样 `for` 循环结束后队列中剩余的节点刚好就是下一层的所有节点，然后进入下一次 `while` 循环。

##### Java 代码实现 #####

/*
    // 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>> ans = new ArrayList<>();
            if(root == null){
        
                return ans;
            }
            Queue<Node> queue = new LinkedList<>();
            queue.offer(root);
    
            while(!queue.isEmpty()){
        
                // 当前层的节点数
                int count = queue.size();
                List<Integer> depthAns = new ArrayList<>();
                for(int i = 0; i < count; i++){
        
                    Node temp = queue.poll();
                    depthAns.add(temp.val);
    
                    // 子节点以此入队
                    List<Node> children = temp.children;
                    if(children != null){
        
                        for(Node c : children){
        
                            queue.offer(c);
                        }
                    }
                }
                ans.add(depthAns);
            }
    
            return ans;
        }
    }

##### Go 代码实现 #####

Go 代码实现的时候，内层循环可以将 `count` 个节点取完后，再统一更新切片 `queue`。

Go语言没有队列这一数据结构，可以使用切片模拟。

/**
     * Definition for a Node.
     * type Node struct {
     *     Val int
     *     Children []*Node
     * }
     */
    
    func levelOrder(root *Node) (ans [][]int) {
        
        if root == nil {
        
            return
        }
    
        queue := []*Node{
        root}
        // 每一层的节点个数
        count := len(queue)
        for count > 0 {
        
            // 每一层的答案；
            levelAns := make([]int, count)
            for i := 0; i < count; i++ {
        
                out := queue[i]
                levelAns[i] = out.Val
    
                // 子节点入队
                children := out.Children
                if children != nil {
        
                    for _, c := range children {
        
                        queue = append(queue, c)
                    }
                }
            }
    
            queue = queue[count:]
            ans = append(ans, levelAns)
            // 计算下一层节点的个数
            count = len(queue)
            
        }
        
        return
        
    }

##### 复杂度分析 #####

**时间复杂度：**  O ( N ) O(N) O(N), `N` 为树中的节点个数，每个节点都有入队和出队两个操作。

**空间复杂度：**  O ( N ) O(N) O(N)，`N` 为树中的节点个数，空间复杂度取决于队列的大小，最大为 `N`。

[3c874b1c65debcc42b05ed76957094fd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/ad281ce54f6443f7bac1b7a43dec8371.png
[1e6a6e109bf6048e467e305402f3959c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/01b3121759ee47babf1a222cf2d70e62.png
[5be39abc2e4cbd9de66ce34c477b5f45.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/c043a78958864a8a938cab7ef34908a1.png
[354f6f3d7e93ef4e1dc933fb7b13cc99.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/bbb74989639248c08ace5109347ddd4b.png
[15768ed2aa5282864cc8cc1a5896a2dc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/8d15f20f4544447283899fb2d5117e61.png