LeetCode 429: N 叉树的层序遍历 N-ary Tree Level Order Traversal

题目:

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

Given an n-ary tree, return the level order traversal of its nodes' values.

例如，给定一个

3叉树

:

返回其层序遍历:

[
     [1],
     [3,2,4],
     [5,6]
] 
           

示例 2:

Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

输入: 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. 树的深度不会超过

   1000

   。
2. 树的节点总数不会超过

   5000

   。

Constraints:

• The height of the n-ary tree is less than or equal to

  1000

• The total number of nodes is between

  [0, 10^4]

解题思路:

层序遍历, 也就是广度优先搜索, 这类题核心解法基本一样. 理论上都可以用递归和队列迭代实现该算法. 详情可以看之前的文章:

队列和 BFS, 栈和 DFS

树的遍历    Traverse a Tree

迭代法:

Java:

class Solution {
    List<List<Integer>> res = new LinkedList<>();

    public List<List<Integer>> levelOrder(Node root) {
        Queue<Node> queue = new LinkedList<>(); // 初始化队列
        if (root == null)
            return res;
        queue.add(root); // 根结点入队
        while (!queue.isEmpty()) { // 队列不空,遍历不止
            int size = queue.size(); // 此时队列的大小就是该层所有结点总数
            LinkedList<Integer> linkedList = new LinkedList<>();
            while (size-- > 0) { // 遍历该层所有结点
                Node node = queue.poll(); // 依次出队
                for (Node cld : node.children) // 该层所有结点的孩子结点依次入队
                    queue.add(cld);
                linkedList.add(node.val); // 存储遍历结果
            }
            res.add(linkedList);
        }
        return res;
    }
}
           

Python:

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        res = list()
        if not root:
            return res
        queue = collections.deque() # 双端队列
        queue.append(root) # 根结点入队
        while queue: # 队列不空,遍历不止
            size = len(queue)# 此时队列的大小就是该层所有结点总数
            tmp = list()
            while(size > 0): # 遍历该层所有结点
                size -= 1
                node = queue.popleft()
                tmp.append(node.val) # 依次出队
                for cld in node.children: # 该层所有结点的孩子结点依次入队
                    queue.append(cld)
            res.append(tmp) # 存储遍历结果
        return res