递归实现二叉树层序遍历是否可行？该实现是否低效或难理解？

有观点认为层序遍历本质上是非递归的，但我认为可以通过非常自然的递归方式实现（Node定义符合预期），代码如下：

static void printKids(List<Node> kids) {
     List<Node> newKids = new ArrayList<>();
     for (var k : kids) {
         System.out.print(" "+k.data+" ");
         if (k.left != null) newKids.add(k.left);
         if (k.right != null) newKids.add(k.right);
     }
     System.out.println("\n");
     if (newKids.size() > 0) printKids(newKids);
 }

请问该实现是否低效或难以理解？唯一略显别扭的是它接收节点列表而非单个节点（如树根节点），但这似乎只是小问题。

效率层面 #

• 时间复杂度和非递归队列实现一致，都是O(n)——每个节点只会被访问一次，没有冗余操作。
• 空间复杂度同样是O(n)：最坏情况（比如完全二叉树的最后一层）下，newKids会存储最多n/2个节点，和队列的空间开销持平。递归调用栈的深度等于树的高度，平衡树里是O(logn)，几乎可以忽略；就算是链式结构的树，调用栈深度是O(n)，但此时newKids每次仅存一个节点，整体空间仍维持在O(n)，和非递归实现没有本质差异。

可读性层面 #

• 这段代码逻辑非常直白：处理当前层所有节点，收集下一层节点，再递归处理下一层。只要理解层序遍历“按层处理”的核心逻辑，很容易看懂。
• 你提到的“接收节点列表而非单个根节点”确实是个小瑕疵，但完全可以通过加一个包装方法解决，让对外接口更符合常规预期：

static void levelOrder(Node root) {
    if (root != null) {
        printKids(Collections.singletonList(root));
    }
}

加了这个方法后，调用时直接传根节点即可，使用体验和常规实现一致。

总结 #

这个递归实现既没有明显的效率问题，也不难理解，完全是层序遍历的一种合理实现。所谓“层序遍历本质是非递归”的说法，更多是因为教学场景里常用队列的非递归实现，但递归实现逻辑自洽，完全站得住脚。

内容的提问来源于stack exchange，提问作者releseabe