/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    List<List<Integer>> nodes = new ArrayList(); // 节点数组，用于保存节点的值
    public List<List<Integer>> levelOrder(TreeNode root) {
        // 从根节点开始向下遍历
        traverse(root, 0);
        return nodes;
    }

    private void traverse(TreeNode root, int k) {
        // 如果不到树的底部就一直递归遍历下去
        if (root != null) {
            // 节点数组长度小于等于k, k在这里表示数的层级深度
            if (nodes.size() <= k) {
                // 向节点数组中添加一个新的二维数组作为占位，也就是开辟新的一层数组空间，用于储存新一层深度的节点
                List<Integer> subNodes = new ArrayList();
                nodes.add(subNodes);
            }
            // 将该层根节点（当前节点）的值添加到节点数组中
            nodes.get(k).add(root.val);
            // 由于有输出顺序要求，所以先递归遍历左子节点及其子树，层级每层加1（因为是子节点，所以层级深度加1）
          // 注意：此处k + 1不能写成 k++，因为 k++ 等价于 k = k + 1，相当于给k本身赋值了，这样会干扰后面右子节点的递归结果
            traverse(root.left, k + 1); 
            // 递归遍历右子节点及其子树，同上
            traverse(root.right, k + 1);
        }
    }
}