Java案例中的二叉树遍历怎么写？

wen java案例 2026-06-19 2

Java案例中的二叉树遍历怎么写？从原理到实战全解析

📚 目录导读

为什么二叉树遍历是Java面试的“硬通货”？
二叉树遍历的三种核心方式与Java实现
实战案例：基于递归与迭代的完整代码
高频问答：面试官最想考你什么？
性能优化与常见坑点

为什么二叉树遍历是Java面试的“硬通货”？

在Java后端开发中,二叉树遍历不仅出现在数据结构与算法的笔试环节，更常出现在实际业务场景，比如文件系统目录解析、表达式树计算、数据压缩（Huffman树），许多开发者能写出递归版遍历，但一到“非递归实现”或“层次遍历变种”就卡壳，究其原因，是对遍历的底层执行流缺乏可视化的理解。

Java案例中的二叉树遍历怎么写？

核心问题：面试官问“手写二叉树遍历”时，他到底在考什么？

递归思维：能否将复杂问题拆解为相似子问题。
栈/队列应用：能否用数据结构模拟系统栈行为。
边界控制：空指针、栈溢出等场景处理是否严谨。

我们接下来将用一个统一的二叉树节点定义，逐步拆解前序、中序、后序、层序遍历的Java案例。

二叉树遍历的三种核心方式与Java实现

1 节点定义（Java标准写法）

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

关键点：left和right指针默认null，这是递归终止的天然条件。

2 递归实现（最易理解）

递归本质是“自己调用自己”，每次调用将当前节点与子节点分离处理。

前序遍历（根 → 左 → 右）：

public void preorder(TreeNode root) {
    if (root == null) return;
    System.out.print(root.val + " ");
    preorder(root.left);
    preorder(root.right);
}

中序遍历（左 → 根 → 右）：

public void inorder(TreeNode root) {
    if (root == null) return;
    inorder(root.left);
    System.out.print(root.val + " ");
    inorder(root.right);
}

后序遍历（左 → 右 → 根）：

public void postorder(TreeNode root) {
    if (root == null) return;
    postorder(root.left);
    postorder(root.right);
    System.out.print(root.val + " ");
}

递归的陷阱：当树深度超过5000层时，Java默认栈会抛出StackOverflowError，此时必须改用迭代实现。

3 迭代实现（用栈模拟系统调用）

迭代版的核心是手动维护一个栈，模拟递归时函数调用的压栈与弹栈。

前序遍历迭代版（关键：先压右孩子，再压左孩子，保证左子树先出栈）：

public void preorderIter(TreeNode root) {
    if (root == null) return;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        System.out.print(node.val + " ");
        if (node.right != null) stack.push(node.right); // 后进先出，所以右先压
        if (node.left != null) stack.push(node.left);
    }
}

中序遍历迭代版（关键：先将所有左孩子压入栈，直到左子树为空，再弹栈并处理右子树）：

public void inorderIter(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) { // 一直往左走，压栈
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        System.out.print(cur.val + " ");
        cur = cur.right; // 转向右子树
    }
}

后序遍历迭代版（技巧：用两个栈或一个栈+标志位，这里展示双栈法）：

public void postorderIter(TreeNode root) {
    if (root == null) return;
    Stack<TreeNode> stack1 = new Stack<>();
    Stack<TreeNode> stack2 = new Stack<>();
    stack1.push(root);
    while (!stack1.isEmpty()) {
        TreeNode node = stack1.pop();
        stack2.push(node);
        if (node.left != null) stack1.push(node.left);
        if (node.right != null) stack1.push(node.right);
    }
    while (!stack2.isEmpty()) {
        System.out.print(stack2.pop().val + " ");
    }
}

原理：stack1按“根、右、左”压栈，stack2反转后得到“左、右、根”。

实战案例：基于递归与迭代的完整代码

下面我们构建一个案例二叉树：

Java代码（含主函数测试）：

public class TreeTraversal {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        System.out.print("前序递归: "); preorder(root);
        System.out.print("\n前序迭代: "); preorderIter(root);
        System.out.print("\n中序递归: "); inorder(root);
        System.out.print("\n中序迭代: "); inorderIter(root);
        System.out.print("\n后序递归: "); postorder(root);
        System.out.print("\n后序迭代: "); postorderIter(root);
    }
    // 此处放置上面的所有方法代码
}

输出结果（所有版本应一致）：
前序：1 2 4 5 3
中序：4 2 5 1 3
后序：4 5 2 3 1

高频问答：面试官最想考你什么？

Q1：递归和迭代哪个性能更好？

A：递归代码简洁，但每层调用都需要压栈，深度大时内存开销高，迭代版手动管理栈，可规避栈溢出，但代码复杂度增加。实际场景：树深度 < 1000 时用递归更可读；深度 > 5000 时必用迭代。

Q2：Morris遍历听过吗？怎样不用栈也不用递归？

A：Morris遍历利用叶子节点的空闲右指针作为线索，实现O(1)额外空间，其核心思想是将当前节点的前驱节点（中序前驱）的右指针临时指向当前节点，遍历结束后再恢复。适用于面试加分，但易出错。

Q3：层序遍历（BFS）怎么写？

A：使用队列（Queue），每层结束后记录当前层节点数，实现逐层输出，常见变种：Zigzag遍历（锯齿形，用双端队列），代码示例：

public void levelOrder(TreeNode root) {
    if (root == null) return;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            System.out.print(node.val + " ");
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        System.out.println(); // 换行表示新一层
    }
}