Java二叉树深度优先遍历方法详解

掌握Java二叉树深度优先遍历技巧，提升算法效率！本文深入解析二叉树深度优先遍历的两种核心实现方式：递归与栈。递归实现思路清晰，通过调整访问顺序实现先序、中序、后序遍历，适用于简单场景。栈实现则显式维护节点栈，模拟递归过程，有效避免栈溢出，更适用于处理复杂树结构。文章还探讨了不同遍历方式的应用场景，如先序遍历用于复制树，中序遍历用于二叉搜索树的有序输出，后序遍历则适用于依赖子节点计算的场景。此外，还简要介绍了Morris遍历等空间优化方法。无论选择递归还是栈，都能高效完成深度优先遍历，助你轻松解决二叉树相关问题。

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

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

解决方案

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

• 递归实现：

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

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

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

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

深度优先遍历主要有三种变种：先序遍历、中序遍历和后序遍历。 区别在于访问根节点的时机。

• 先序遍历（Preorder Traversal）： 先访问根节点，然后访问左子树，最后访问右子树。（根左右）
• 中序遍历（Inorder Traversal）： 先访问左子树，然后访问根节点，最后访问右子树。（左根右）
• 后序遍历（Postorder Traversal）： 先访问左子树，然后访问右子树，最后访问根节点。（左右根）

上面的递归和栈实现的例子，都是先序遍历。 要实现中序和后序遍历，只需要调整访问根节点的时机即可。

如何根据实际问题选择合适的遍历方式？

选择哪种遍历方式，取决于实际问题的需求。

• 先序遍历： 常用于复制树结构，因为先创建根节点，再创建子节点。
• 中序遍历： 常用于二叉搜索树，因为中序遍历的结果是一个有序序列。
• 后序遍历： 常用于计算目录树的大小，因为需要先计算子目录的大小，才能计算父目录的大小。

举个例子，如果你要判断一棵树是否是二叉搜索树，用中序遍历最方便，因为可以得到一个有序序列，只需要判断这个序列是否递增即可。

除了递归和栈，还有其他实现深度优先遍历的方式吗？

理论上来说，只要能模拟递归的过程，都可以用来实现深度优先遍历。 例如，可以使用迭代器模式，或者使用 Continuation。 但是，递归和栈是最常用的，也是最容易理解的。

另外，如果树的结构可以修改，可以使用 Morris 遍历，它不需要额外的空间，就可以实现中序遍历。 Morris 遍历的思路比较巧妙，它通过修改节点的指针，将树转换成一个链表，然后再遍历这个链表。 不过 Morris 遍历会改变树的结构，所以需要谨慎使用。

以上就是《Java二叉树深度优先遍历方法详解》的详细内容，更多关于递归,栈,二叉树,深度优先遍历,遍历方式的资料请关注golang学习网公众号！