java代码怎样实现二叉树的深度优先遍历 java代码树遍历的实用实现技巧-java教程-PHP中文网

java代码怎样实现二叉树的深度优先遍历 java代码树遍历的实用实现技巧

爱谁谁

发布： 2025-08-11 21:12:02

原创

935人浏览过

二叉树的深度优先遍历可通过递归和栈实现，1. 递归实现思路直观，按先序（根左右）、中序（左根右）、后序（左右根）调整访问顺序；2. 栈实现通过显式维护节点栈模拟递归过程，需先压入右子节点再压入左子节点以确保左子树优先访问；3. 实际应用中根据需求选择遍历方式：先序用于复制树，中序用于二叉搜索树的有序输出，后序用于依赖子节点计算的场景；4. 除递归和栈外，还可使用morris遍历等空间优化方法，但会修改树结构。两种主要实现方式均能完成深度优先遍历且结果一致。

java代码怎样实现二叉树的深度优先遍历 java代码树遍历的实用实现技巧

二叉树的深度优先遍历，说白了就是沿着树的深度方向一路走到底，先把左边走完，再走右边。实现起来，递归和栈是两个好帮手。

解决方案

深度优先遍历（DFS）的核心在于“先深后广”，体现在代码上，就是先访问一个节点的子节点，再访问兄弟节点。下面分别用递归和栈来实现：

立即学习“Java免费学习笔记（深入）”；

递归实现：

递归的思路非常直观，就是不断调用自身来访问子节点。

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

public class BinaryTreeDFS {

    public void dfsRecursive(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " "); // 先访问根节点
        dfsRecursive(root.left);       // 再访问左子树
        dfsRecursive(root.right);      // 最后访问右子树
    }

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

        BinaryTreeDFS dfs = new BinaryTreeDFS();
        System.out.println("递归方式深度优先遍历结果：");
        dfs.dfsRecursive(root); // 输出：1 2 4 5 3
    }
}

登录后复制

这段代码就是一个典型的先序遍历，先访问根节点，然后递归地访问左子树和右子树。容易理解，但如果树太深，可能会导致栈溢出。

栈实现：

用栈来模拟递归的过程，避免栈溢出。

import java.util.Stack;

public class BinaryTreeDFS {

    public void dfsStack(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 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);

        BinaryTreeDFS dfs = new BinaryTreeDFS();
        System.out.println("栈方式深度优先遍历结果：");
        dfs.dfsStack(root); // 输出：1 2 4 5 3
    }
}

登录后复制

这里，我们用一个栈来保存待访问的节点。每次从栈顶取出一个节点，访问它，然后将它的右子节点和左子节点依次入栈。注意入栈的顺序，要先右后左，才能保证左子节点先被访问。

深度优先遍历有哪些常见的变种？