一种简单的递归层序遍历方法？

Question

我看到的答案表明，层序遍历本质上是非递归的。我建议它可以以一种非常自然的方式递归完成（节点按预期定义）：

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);
 }

这是否效率低下或难以理解？一个有点尴尬的事情是，它不是采用节点作为参数（如树的根节点），而是采用节点列表，但这似乎是一个小问题。

Answer 1

这段代码很好，但是递归的使用实际上归结为尾递归。但由于 Java 没有实现尾部调用消除，因此这使用了实际上没有必要的调用堆栈空间。

您已经用尾递归调用有效地替换了循环，而大多数人更愿意做相反的事情，以节省堆栈的内存使用。