题目描述

某公司用一棵二叉树表示组织架构：根节点是公司的 $CEO$，其余节点是员工。每个节点上的值是该员工的职位编号。每位管理者至多有两名直接下属，分别对应左、右子节点。

请按从上到下、同一层从左到右的顺序，给出每一层员工的职位编号。

示例：

假设组织架构如下：

      5
    /   \
   1     8
  / \
 3   6

则各层职位编号为：

[
 [5],
 [1, 8],
 [3, 6]
]

评测会根据输入构建二叉树，并调用你实现的接口 levelOrder(root)：参数 root 为根节点（TreeNode，含整型 val 以及左右孩子 left、right），返回按层划分的二维整数数组。空缺节点不出现在答案中。

输入描述

输入仅一行，给出这棵二叉树的层序序列化，格式为：

{v1,v2,...,vk}

其中各字段用逗号分隔；# 表示空节点。序列化顺序与层序遍历一致（先左后右）。

输出描述

输出一行，为按层划分的二维数组，层与层之间、同一层从左到右排列。格式与样例一致（括号嵌套，逗号分隔，不含空格）。

样例1

输入

{12,5,9,7,#,#,4}

输出

[[12],[5,9],[7,4]]

说明

对应的组织架构为：

      12
     /  \
    5    9
   /      \
  7        4

• 第 $1$ 层只有 $CEO$，职位编号为 $12$。
• 第 $2$ 层从左到右为 $5$、$9$。
• 第 $3$ 层：$5$ 的左下属为 $7$，$9$ 的右下属为 $4$；空缺位置不输出。

因此答案为 [[12],[5,9],[7,4]]。若误把第 $3$ 层写成 [7,4] 以外的顺序，或把空节点也填进数组，则与题意不符。

样例2

输入

{10,4,15,#,#,8,2}

输出

[[10],[4,15],[8,2]]

说明

对应的组织架构为：

      10
     /  \
    4    15
        /  \
       8    2

• 第 $1$ 层：$10$。
• 第 $2$ 层从左到右：$4$、$15$。
• 第 $3$ 层：$4$ 没有下属；$15$ 的左、右下属分别为 $8$、$2$。

因此答案为 [[10],[4,15],[8,2]]。另一棵把 $8$ 挂到 $4$ 下面的树序列化结果不同，不是本组输入。

提示

• 节点总数 $\le 1000$
• 职位编号为整数
• 输入保证是一棵合法二叉树的层序序列化