二叉树的深度优先遍历可通过递归和栈实现，1. 递归实现思路直观，按先序（根左右）、中序（左根右）、后序（左右根）调整访问顺序；2. 栈实现通过显式维护节点栈模拟递归过程，需先压入右子节点再压入左子节点以确保左子树优先访问；3. 实际应用中根据需求选择遍历方式：先序用于复制树，中序用于二叉搜索树的有序输出，后序用于依赖子节点计算的场景；4. 除递归和栈外，还可使用morris遍历等空间优化方法，但会修改树结构。两种主要实现方式均能完成深度优先遍历且结果一致。
二叉树的深度优先遍历，说白了就是沿着树的深度方向一路走到底，先把左边走完，再走右边。实现起来，递归和栈是两个好帮手。
解决方案
深度优先遍历（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 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 遍历会改变树的结构，所以需要谨慎使用。
