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

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

示例 1：
image.png

输入：root = [1,null,3,2,4,null,5,6]
输出：[[1],[3,2,4],[5,6]]
示例 2：
image.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
树的节点总数在 [0, 10^4] 之间

  1. class Solution {
  2.     public List<List<Integer>> levelOrder(Node root) {
  3.         List<List<Integer>> res = new ArrayList<>();
  4.         if (root == null) return res;
  5.         Deque<Node> q = new LinkedList<>();
  6.         q.addLast(root);
  7.         while (!q.isEmpty()) {
  8.             int size = q.size();
  9.             List<Integer> list = new ArrayList<>();
  10.             while (size -- > 0) {
  11.                 Node t = q.pollFirst();
  12.                 List<Node> tt = t.children;
  13.                 for (int i = 0; i < tt.size(); ++i) 
  14.                     q.addLast(tt.get(i));
  15.                 list.add(t.val);
  16.             }
  17.             res.add(new ArrayList(list));
  18.         }
  19.         return res;
  20.     }
  21. }

dfs

  1. /*
  2. // Definition for a Node.
  3. class Node {
  4.     public int val;
  5.     public List<Node> children;
  7.     public Node() {}
  9.     public Node(int _val) {
  10.         val = _val;
  11.     }
  13.     public Node(int _val, List<Node> _children) {
  14.         val = _val;
  15.         children = _children;
  16.     }
  17. };
  18. */
  20. class Solution {
  21.     //dfs
  22.     Map<Integer, List<Integer>> map;    //存每一层的
  23.     int maxi;
  24.     public List<List<Integer>> levelOrder(Node root) {
  25.         List<List<Integer>> res = new ArrayList<>();
  26.         if (root == null) return res;
  27.         map = new HashMap<>();
  28.         dfs(root, 0);
  29.         for (int i = 0; i <= maxi; ++i) res.add(map.get(i));
  30.         return res;
  31.     }
  33.     void dfs(Node root, int depth) {
  34.         if (root == null) return;
  35.         maxi = Math.max(maxi, depth);
  36.         List<Integer> list = map.getOrDefault(depth, new ArrayList<Integer>());
  37.         list.add(root.val);
  38.         map.put(depth, list);
  39.         for (Node node : root.children) dfs(node, depth + 1);
  40.     }
  41. }