最好先看一下LeetCode关于树的串行化格式和实际结构的说明。第一遍写理解得出了些偏差，吃了点亏。

解法一：广度优先遍历

第一遍写的。用了各种标志来记录以保证正确维护遍历深度。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  * int val;
  5.  * TreeNode left;
  6.  * TreeNode right;
  7.  * TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  11. /**
  12.  * Definition for singly-linked list.
  13.  * public class ListNode {
  14.  *     int val;
  15.  *     ListNode next;
  16.  *     ListNode(int x) { val = x; }
  17.  * }
  18.  */
  20. class Solution {
  21.     public ListNode[] listOfDepth(TreeNode tree) {
  22.         // BFS队列
  23.         Queue<TreeNode> queue = new LinkedList<>();
  24.         // 答案
  25.         List<ListNode> list = new LinkedList<>();
  26.         queue.offer(tree);
  28.         // 当前遍历深度
  29.         int depth = 0;
  31.         // 当前层最后一个结点
  32.         TreeNode lastTreeNode = tree;
  34.         // 下一层最后一个孩子结点
  35.         TreeNode tail = tree;
  37.         // 当前层已加入答案的最后一个结点
  38.         ListNode lastListNode = null;
  40.         while (!queue.isEmpty()) {
  41.             TreeNode tmp = queue.poll();
  43.             // 该层的第一个结点
  44.             if (list.size() == depth) {
  45.                 lastListNode = new ListNode(tmp.val);
  46.                 list.add(lastListNode);
  47.             } else {
  48.                 ListNode newNode = new ListNode(tmp.val);
  49.                 lastListNode.next = newNode;
  50.                 lastListNode = newNode;
  51.             }
  53.             if (tmp.left != null) {
  54.                 queue.offer(tmp.left);
  55.                 tail = tmp.left;
  56.             }
  57.             if (tmp.right != null) {
  58.                 queue.offer(tmp.right);
  59.                 tail = tmp.right;
  60.             }
  62.             // 当前层已经全部遍历完，进入下一层
  63.             if (tmp == lastTreeNode) {
  64.                 ++depth;
  65.                 lastTreeNode = tail;
  66.             }
  67.         }
  68.         ListNode[] ans = new ListNode[depth];
  69.         return list.toArray(ans);
  70.     }
  71. }

解法二：简化解法一

提交完解法一看了下其他人的解法，发现之前自己写复杂了，只需要先记录该层的结点数，然后通过循环全部遍历完就可以直接进入下一层。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. /**
  11.  * Definition for singly-linked list.
  12.  * public class ListNode {
  13.  *     int val;
  14.  *     ListNode next;
  15.  *     ListNode(int x) { val = x; }
  16.  * }
  17.  */
  19. class Solution {
  20.     public ListNode[] listOfDepth(TreeNode tree) {
  21.         // BFS队列
  22.         Queue<TreeNode> queue = new LinkedList<>();
  23.         // 答案
  24.         List<ListNode> list = new LinkedList<>();
  25.         queue.offer(tree);
  27.         // 当前遍历深度
  28.         int depth = 0;
  30.         // 当前层已加入答案的最后一个结点
  31.         ListNode lastListNode = null;
  33.         while (!queue.isEmpty()) {
  34.             int size = queue.size();
  36.             for (int i = 0; i < size; ++i) {
  37.                 TreeNode tmp = queue.poll();
  39.                 // 该层的第一个结点
  40.                 if (i == 0) {
  41.                     lastListNode = new ListNode(tmp.val);
  42.                     list.add(lastListNode);
  43.                 } else {
  44.                     ListNode newNode = new ListNode(tmp.val);
  45.                     lastListNode.next = newNode;
  46.                     lastListNode = newNode;
  47.                 }
  49.                 if (tmp.left != null) {
  50.                     queue.offer(tmp.left);
  51.                 }
  52.                 if (tmp.right != null) {
  53.                     queue.offer(tmp.right);
  54.                 }
  55.             }
  57.             ++depth;
  58.         }
  59.         ListNode[] ans = new ListNode[depth];
  60.         return list.toArray(ans);
  61.     }
  62. }