能否通过深度优先遍历实现二叉树层级的逐行打印？

嘿，这个问题问得很到位！咱们来一步步拆解你的疑问：

能不能用前/中/后序遍历实现二叉树的逐行打印？ #

当然可以！核心就是你代码里已经定义的depth参数——它能帮你追踪当前节点所在的层级，只要利用好这个参数，就能把同一层的节点归到一起打印。

怎么利用depth参数实现逐行打印？ #

你之前的代码只是单纯打印每个节点，没有区分层级。这里给你两种可行的思路：

思路1：逐层递归打印（空间优化到O(h)）

这种方法不需要存储所有节点，而是先计算树的高度，然后对每一层单独进行遍历打印。空间复杂度是树的高度h（递归栈的深度），比你说的链表数组O(n)空间更优，尤其是平衡树的情况下h=logn，远小于n。

修改你的代码如下：

class Node {
    int key;
    Node left;
    Node right;
    Node(int value) {
        key = value;
        left = null;
        right = null;
    }
}

public class bst {
    private Node root;
    bst() { root = null; }

    // 补全插入方法方便测试
    void insert(int key) {
        root = insertRec(root, key);
    }
    private Node insertRec(Node root, int key) {
        if (root == null) {
            root = new Node(key);
            return root;
        }
        if (key < root.key)
            root.left = insertRec(root.left, key);
        else if (key > root.key)
            root.right = insertRec(root.right, key);
        return root;
    }

    // 获取树的高度
    private int getHeight(Node root) {
        if (root == null) return 0;
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return Math.max(leftHeight, rightHeight) + 1;
    }

    // 打印指定层级的所有节点
    private void printLevel(Node root, int currentLevel) {
        if (root == null) return;
        // 当前层级匹配，打印节点
        if (currentLevel == 0) {
            System.out.print(root.key + " ");
        } else {
            // 递归遍历下一层的左右子树
            printLevel(root.left, currentLevel - 1);
            printLevel(root.right, currentLevel - 1);
        }
    }

    void printTree() {
        int height = getHeight(root);
        // 逐层打印
        for (int i = 0; i < height; i++) {
            printLevel(root, i);
            System.out.println(); // 每一层结束后换行
        }
    }

    public static void main(String[] Args) {
        bst tree = new bst();
        tree.insert(25);
        tree.insert(15);
        tree.insert(35);
        tree.insert(7);
        tree.insert(18);
        tree.insert(33);
        tree.insert(36);
        tree.printTree();
    }
}

这个方法的小缺点是时间复杂度是O(n*h)——因为每个节点会被访问多次（比如第k层的节点会被递归遍历k+1次），比队列层序遍历的O(n)稍慢，但空间上更省。

思路2：迭代遍历+栈存深度（时间O(n)，空间O(h)）

如果想同时保证O(n)时间和O(h)空间，可以用栈来记录节点和对应的深度，模拟前序遍历的过程，同时跟踪当前层级来控制换行：

import java.util.Stack;
import javafx.util.Pair; // 也可以自己实现一个简单的Pair类

// （Node和bst的基础代码同上，这里只修改printTree方法）
void printTreeIterative() {
    if (root == null) return;
    Stack<Pair<Node, Integer>> stack = new Stack<>();
    stack.push(new Pair<>(root, 0));
    int currentDepth = 0;

    while (!stack.isEmpty()) {
        Pair<Node, Integer> pair = stack.pop();
        Node node = pair.getKey();
        int depth = pair.getValue();

        // 深度变化时换行
        if (depth > currentDepth) {
            System.out.println();
            currentDepth = depth;
        }
        System.out.print(node.key + " ");

        // 栈是后进先出，先压右子树再压左子树，保证前序遍历的根→左→右顺序
        if (node.right != null) {
            stack.push(new Pair<>(node.right, depth + 1));
        }
        if (node.left != null) {
            stack.push(new Pair<>(node.left, depth + 1));
        }
    }
}

这个方法每个节点只被访问一次，时间O(n)，栈的最大大小是树的高度h，空间O(h)，完美平衡了时间和空间。

关于你提到的链表数组存储的方案 #

那个方案确实是O(n)空间，适合需要保存所有层节点的场景，但如果只是单纯逐行打印，上面两种方法的空间效率更高。

总结一下：

• 前/中/后序遍历完全可以实现逐行打印，核心是用depth参数追踪层级；
• 追求空间最优选逐层递归法（O(h)空间），追求时间空间平衡选迭代栈方法（O(n)时间+O(h)空间）。

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