java怎么遍历二叉树

一、二叉树遍历基础认知

遍历是访问二叉树中所有节点的过程,是二叉树操作的基石。在Java中,遍历不仅是算法练习的基础内容,更是面试高频考点与实际开发中处理树形数据结构的必经之路。二叉树遍历分为四种基本类型:前序遍历(根→左→右)、中序遍历(左→根→右)、后序遍历(左→右→根)和层序遍历(按层级从上到下、从左到右)。

这四类遍历方式并非孤立存在,而是相互关联、可相互转换的。例如:中序+前序可唯一确定一棵二叉树;中序+后序亦可唯一还原树结构;但前序+后序则无法唯一确定。理解每种遍历的逻辑本质与应用场景,是掌握java怎么遍历二叉树的关键。

值得注意的是,遍历的实现方式直接决定了算法的时间与空间复杂度表现。递归方式代码简洁、逻辑清晰,但受系统栈深度限制;迭代方式虽需手动管理栈或队列,却更适用于深度较大的树结构。而 Morris 遍历则在保持 O(n) 时间复杂度的同时,将空间复杂度降至 O(1),是面试中的高阶考点。

为什么遍历如此重要?

从理论角度看,遍历是理解树结构内在关系的唯一途径;从工程实践出发,它直接关联着文件系统解析、XML/JSON树解析、表达式求值、数据库索引(B+树)、编译器语法树处理等核心场景。例如,Java编译器在解析源码时,会将语法结构构建成抽象语法树(AST),而遍历AST正是进行代码分析、重构与优化的第一步。

此外,遍历顺序的选择直接影响业务逻辑。例如,中序遍历二叉搜索树(BST)会得到有序序列,这在需要排序输出的场景中极为关键;层序遍历则天然适用于最短路径问题,如在社交网络中寻找最短好友链。

二、四种遍历方式详解

1. 前序遍历(Preorder Traversal)

前序遍历的顺序为:**访问根节点 → 前序遍历左子树 → 前序遍历右子树**。其典型应用场景包括:复制二叉树(先创建根节点再构建子树)、表达式树的前缀表示(如 + * A B C 表示 (A*B)+C)。

以如下二叉树为例:

      A
     / \
    B   C
   / \   \
  D   E   F

前序遍历结果为:A → B → D → E → C → F

递归实现逻辑清晰,但需警惕栈溢出风险;迭代实现需借助栈模拟系统调用栈,关键点在于:**先压右子树再压左子树**,以保证左子树先出栈处理。

2. 中序遍历(Inorder Traversal)

中序遍历的顺序为:**中序遍历左子树 → 访问根节点 → 中序遍历右子树**。这是二叉搜索树(BST)的“黄金遍历”——输出结果严格递增。在数据库索引(如MySQL InnoDB的B+树)中,中序遍历用于高效获取有序键值范围。

对上述示例树进行中序遍历,结果为:D → B → E → A → C → F

递归实现简单直接;迭代实现需持续向左走并压栈,遇到空节点时弹栈并转向右子树。此过程需精确控制栈状态与指针移动,是理解非递归遍历机制的入门范例。

3. 后序遍历(Postorder Traversal)

后序遍历的顺序为:**后序遍历左子树 → 后序遍历右子树 → 访问根节点**。其核心价值在于“自底向上”的计算模式:先处理子节点再处理父节点,适用于目录删除、表达式树求值、释放树资源等场景。

对示例树的后序遍历结果为:D → E → B → F → C → A

递归实现自然;迭代实现需双重栈或单栈+前驱指针。难点在于判断“何时可安全访问根节点”——只有当左右子树均处理完毕(或为空)时,根节点才可出栈访问。常见错误是未正确维护前驱节点指针,导致节点重复入栈或遗漏访问。

4. 层序遍历(Level Order Traversal)

层序遍历按层级顺序访问节点,使用**队列**实现。其典型应用包括:二叉树宽度计算(每层节点数的最大值)、打印树的边界节点、二叉树的Z字形遍历等高级变体。

对示例树的层序遍历结果为:A → B → C → D → E → F

实现要点在于:**按层入队**。每次处理队列中当前层的所有节点(可通过记录队列当前大小实现),再将下一层节点入队。若需区分层级(如打印每层节点),需在队列中存储节点及层级信息,或使用双队列交替。

三、递归与非递归实现对比

递归实现:简洁性与局限性

递归方式代码可读性高,逻辑与定义一致,是教学与快速实现的首选。但其本质是系统栈的隐式调用,当树深度过大时(如退化为链表的BST),可能导致StackOverflowError。

以中序遍历为例:

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

该实现中,递归深度等于树高h,空间复杂度为O(h);每个节点仅访问一次,时间复杂度为O(n)。

迭代实现:手动栈控制

迭代方式通过显式栈模拟递归过程,避免系统栈溢出,适用于深度较大的树。以中序遍历为例,其核心逻辑为:一路向左压栈 → 遇空弹栈访问 → 转向右子树。

public static void inorderIterative(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode curr = root;
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        curr = stack.pop();
        System.out.print(curr.val + " ");
        curr = curr.right;
    }
}

关键点:curr指针在“向左走”与“处理节点”间切换;栈仅存储待处理的路径节点,空间复杂度仍为O(h),但由JVM堆栈管理,更稳定。

Morris遍历:O(1)空间复杂度的奇迹

Morris遍历通过**临时修改树结构**(建立线索二叉树)实现无栈遍历,空间复杂度降为O(1)。其核心思想是:利用叶子节点的空right指针指向中序后继节点,遍历完成后恢复原树结构。

以中序遍历为例,步骤如下:

  • 若当前节点左子树为空,访问该节点并转向右子树
  • 若左子树不为空,找到其前驱节点(左子树最右节点)
  • 若前驱节点的right为空,则指向当前节点,转向左子树
  • 若前驱节点的right已指向当前节点(说明左子树已访问),恢复其right为null,访问当前节点,转向右子树
public static void inorderMorris(TreeNode root) {
    TreeNode curr = root;
    while (curr != null) {
        if (curr.left == null) {
            System.out.print(curr.val + " ");
            curr = curr.right;
        } else {
            TreeNode pre = curr.left;
            while (pre.right != null && pre.right != curr) {
                pre = pre.right;
            }
            if (pre.right == null) {
                pre.right = curr;
                curr = curr.left;
            } else {
                pre.right = null;
                System.out.print(curr.val + " ");
                curr = curr.right;
            }
        }
    }
}

注意:Morris遍历会短暂修改树结构,需确保操作完成后恢复。适用于内存受限场景(如嵌入式设备处理日志树),但调试复杂度较高。

四、完整可运行代码示例

二叉树节点定义与测试用例

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
public class BinaryTreeTraversal {
    public static void main(String[] args) {
        // 构建示例树:
        //       A(1)
        //      /    \
        //   B(2)   C(3)
        //   /  \      \
        // D(4) E(5)  F(6)
        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);
        root.right.right = new TreeNode(6);
        System.out.println("=== 前序遍历 ===");
        preorderRecursive(root);
        System.out.println();
        System.out.println("=== 中序遍历 ===");
        inorderRecursive(root);
        System.out.println();
        System.out.println("=== 后序遍历 ===");
        postorderRecursive(root);
        System.out.println();
        System.out.println("=== 层序遍历 ===");
        levelOrder(root);
    }
    // 递归遍历方法...
}

四种遍历的递归实现(完整代码)

public static void preorderRecursive(TreeNode root) {
    if (root == null) return;
    System.out.print(root.val + " ");
    preorderRecursive(root.left);
    preorderRecursive(root.right);
}
public static void inorderRecursive(TreeNode root) {
    if (root == null) return;
    inorderRecursive(root.left);
    System.out.print(root.val + " ");
    inorderRecursive(root.right);
}
public static void postorderRecursive(TreeNode root) {
    if (root == null) return;
    postorderRecursive(root.left);
    postorderRecursive(root.right);
    System.out.print(root.val + " ");
}
public static void levelOrder(TreeNode root) {
    if (root == null) return;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        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);
    }
}

迭代与Morris遍历完整实现

// 迭代中序遍历
public static void inorderIterative(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode curr = root;
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        curr = stack.pop();
        System.out.print(curr.val + " ");
        curr = curr.right;
    }
}
// Morris中序遍历
public static void inorderMorris(TreeNode root) {
    TreeNode curr = root;
    while (curr != null) {
        if (curr.left == null) {
            System.out.print(curr.val + " ");
            curr = curr.right;
        } else {
            TreeNode pre = curr.left;
            while (pre.right != null && pre.right != curr) {
                pre = pre.right;
            }
            if (pre.right == null) {
                pre.right = curr;
                curr = curr.left;
            } else {
                pre.right = null;
                System.out.print(curr.val + " ");
                curr = curr.right;
            }
        }
    }
}
// 迭代前序遍历(双栈法)
public static void preorderIterative(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 + " ");
    }
}

五、高频应用场景与实战案例

1. 表达式树求值

表达式树是二叉树的典型应用。例如,表达式 (3 + 5) * (2 - 1) 对应的树结构为:

          *
        /   \
       +     -
      / \   / \
     3  5  2  1

后序遍历结果为:3 5 + 2 1 - *,对应逆波兰表达式,可直接用栈求值。Java实现中,遍历过程中遇到操作数入栈,遇到操作符弹出两数计算后入栈,最终栈顶即结果。

2. 二叉搜索树(BST)的中序遍历特性

在BST中,中序遍历结果严格递增。利用此特性,可解决:验证BST合法性、查找第k小元素、恢复被错误交换的两个节点(LeetCode 99题)。

例如,若BST中节点5与节点2被错误交换,中序遍历结果将出现逆序对:... 3, 5, 4, 2, 6 ...。第一个逆序对的较大值(5)与第二个逆序对的较小值(2)即为需交换的节点。

3. 文件系统目录树遍历

操作系统的目录结构本质是树。在Java中,java.nio.file.Files.walkFileTree() 方法使用Visitor模式实现深度优先遍历(类似后序遍历),允许在进入/离开目录或访问文件时执行自定义操作。

Files.walkFileTree(Paths.get("/home/user"), new SimpleFileVisitor<Path>() {
    @Override
    public FileVisitResult visitFile(Path file, BasicFileAttributes attrs) {
        System.out.println("文件: " + file);
        return FileVisitResult.CONTINUE;
    }
    @Override
    public FileVisitResult postVisitDirectory(Path dir, IOException exc) {
        System.out.println("目录结束: " + dir);
        return FileVisitResult.CONTINUE;
    }
});

此设计完美契合后序遍历“先处理子目录再处理父目录”的逻辑,确保目录删除时先清空内容。

4. 二叉树的序列化与反序列化

通过前序+中序或后序+中序遍历结果可唯一确定一棵二叉树。序列化时,将树结构转为字符串;反序列化时,根据遍历序列重建树。

例如,前序序列 [1,2,4,5,3,6] 与中序序列 [4,2,5,1,3,6] 可重建原始树。反序列化过程使用递归:前序首元素为根,在中序序列中定位根,分割左右子树,递归构建。

六、常见误区与调试技巧

误区1:混淆递归终止条件

错误写法:if (root.left == null && root.right == null) return; —— 仅处理叶子节点,忽略单子树节点。正确终止条件应为:if (root == null) return;。

误区2:迭代实现中栈状态管理错误

例如,后序遍历迭代实现中,若未正确判断“是否已访问右子树”,会导致节点重复入栈。解决方案:使用前驱指针记录上一访问节点,若当前节点的右子树为前驱节点,则可安全访问当前节点。

误区3:Morris遍历未恢复树结构

若在Morris遍历中未将临时线索指针恢复为null,将导致后续操作异常(如树结构被破坏)。务必在访问节点后执行 pre.right = null;。

调试技巧

  • 使用打印语句标记节点访问顺序,验证逻辑正确性
  • 对小规模树结构手动推演遍历路径
  • 利用IDE调试功能单步跟踪栈状态变化
  • 编写单元测试覆盖边界情况(空树、单节点、退化链表)

七、面试真题深度解析

Q1:如何验证一棵树是否为二叉搜索树?

解法1:中序遍历法——遍历结果应严格递增,时间O(n),空间O(h)。

解法2:上下界递归法——每个节点需满足 min < val < max,递归时传递边界值。时间O(n),空间O(h)。

解法3:Morris中序遍历——空间O(1),但实现复杂。

推荐使用解法2,代码简洁且易理解:

public boolean isValidBST(TreeNode root) {
    return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean isValidBST(TreeNode node, long min, long max) {
    if (node == null) return true;
    if (node.val <= min || node.val >= max) return false;
    return isValidBST(node.left, min, node.val) &&
           isValidBST(node.right, node.val, max);
}

Q2:求二叉树的最大深度

递归解法:深度 = 1 + max(左子树深度, 右子树深度)

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

层序遍历解法:统计层数

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    int depth = 0;
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        depth++;
    }
    return depth;
}

Q3:如何判断两棵树是否完全相同?

前序+中序序列唯一确定一棵树。若两棵树的前序、中序遍历结果均相同,则树结构相同。但更高效的做法是直接递归比较:

public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) return true;
    if (p == null || q == null) return false;
    if (p.val != q.val) return false;
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

九、FAQ常见问题解答

Q:为什么我的中序遍历结果不是有序的?

A:可能原因:1 输入的不是二叉搜索树;2 遍历逻辑错误(如混淆了中序与前序);3 节点值比较时未处理null。请检查节点定义与遍历代码逻辑。

Q:层序遍历如何实现每层换行?

A:在队列中存储节点及层级信息,或使用双队列交替。示例代码:

public void levelOrderByLine(TreeNode root) {
    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(); // 换行
    }
}

Q:如何打印二叉树的右视图?

A:层序遍历中,每层最后一个节点即右视图节点。修改代码为:

public List<Integer> rightSideView(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    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();
            if (i == size - 1) result.add(node.val); // 仅记录每层最后一个
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
    }
    return result;
}