详解Java中如何通过递归算法实现按层遍历二叉树

声明一个表示二叉树节点的静态内部类 TreeNode ， 图示，通过该类对象可以构建一棵二叉树结构。

编写一个方法，通过递归调用的方式，获取一棵二叉树的高度，步骤如下：

1. 如果参数节点为空，则返回高度 0；

2. 否则递归调用该算法，分别获取节点左右子树的高度；

3. 左右子树高度的较大值加 1 即以当前节点为根的二叉树的高度。

编写基于递归调用的算法，实现按层遍历一棵二叉树，其包含3个参数：

1. 当前遍历的二叉树节点；

2. 存放结果的嵌套列表，内层列表分别表示每一层的遍历结果；

3. 表示当前遍历的二叉树层数（从 0 开始，0 即代表二叉树第 1 层）。

算法实现步骤如下：

1. 如果遍历的阶段为空，则直接返回；

2. 否则通过递归调用遍历其左右子树，对应的表示层数的第3个参数加 1；

3. 将当前节点的值添加到该层对应的结果数据结构中（即第2个参数）。

综合上述算法，实现一个方法，可广度优先遍历一棵二叉树：

1. 调用算法获取二叉树的高度；

2. 通过二叉树的高度，构建一个存储按层遍历二叉树结果的嵌套列表；

3. 调用递归算法，按层遍历二叉树，从第 0 层开始遍历。

创建本地测试主方法：

1. 构建一棵二叉树；

2. 按层遍历二叉树，并将遍历结果打印到控制台。

运行本地测试主方法，观察控制台输出，图示，符合预期，按层遍历二叉树的递归算法测试通过。其时间复杂度为 O(N)，N 即二叉树的节点数量。