树的基本结构是数据结构中非常重要的概念，它由节点和边组成，其中每个节点可以有多个子节点（子树），但只有一个父节点（根节点除外）。比如，一棵家族树中，最上面的“爷爷”是根，他的儿子是一级子节点，孙子是二级子节点，直到没有子节点的“叶子”节点。
什么是DFS？¶
DFS（Depth-First Search，深度优先搜索）是一种遍历或搜索方法，核心思想是“一条路走到黑，走不通再回头”。想象你在迷宫中探险，先选一条路往前走，直到无法继续（比如遇到死胡同），再回到岔路口选下一条路。这种“深入到底，再回溯”的方式，就是DFS的特点。
树的DFS遍历分类¶
在树中，DFS遍历通常分为三种：前序遍历（根→左→右）、中序遍历（左→根→右）、后序遍历（左→右→根）。其中，前序遍历（根→左→右）最直接体现“从根到叶”的路径，因为它先访问当前节点（根），再递归处理左子树，最后处理右子树，恰好覆盖了从根到每个叶子的完整路径。
递归实现前序遍历（根到叶路径）¶
递归是实现DFS的直观方式，因为它天然符合“深入子树”的逻辑。以下是递归前序遍历的步骤：
1. 访问当前节点：先处理当前节点（例如打印节点值）；
2. 递归处理左子树：如果有左子节点，递归执行前序遍历；
3. 递归处理右子树：如果有右子节点，递归执行前序遍历。
示例：以一棵简单二叉树为例（根为1，左子树2，右子树3；2的左子树4，右子树5）：
1
/ \
2 3
/ \
4 5
递归过程：
- 访问1 → 递归左子树2 → 访问2 → 递归左子树4 → 访问4（无左/右子树，返回）→ 递归右子树5 → 访问5（无左/右子树，返回）→ 递归右子树3 → 访问3（无左/右子树，返回）。
- 最终访问顺序：1 → 2 → 4 → 5 → 3。
伪代码（Python风格）：
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def dfs_preorder(node):
if node is None: # 空节点直接返回
return
print(node.val, end=" ") # 访问当前节点
dfs_preorder(node.left) # 递归左子树
dfs_preorder(node.right) # 递归右子树
# 构建示例树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
# 调用函数，输出根到叶路径
dfs_preorder(root) # 输出：1 2 4 5 3
非递归实现前序遍历（用栈）¶
递归需要调用函数自身，而DFS的“深度优先”也可以用栈来模拟（栈是“后进先出”的数据结构）。非递归前序遍历的步骤：
1. 初始化栈：将根节点入栈；
2. 循环处理栈顶节点：
- 弹出栈顶节点，访问它；
- 先右后左将子节点入栈（因为栈“后进先出”，先入右子树会导致左子树先被弹出处理）；
3. 终止条件：栈为空时遍历结束。
伪代码（Python风格）：
def dfs_preorder_iterative(root):
if root is None:
return
stack = [root] # 初始化栈，根节点入栈
while stack:
node = stack.pop() # 弹出栈顶节点
print(node.val, end=" ") # 访问当前节点
# 先右后左入栈，保证左子树先被处理
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
# 调用函数，输出结果同上
dfs_preorder_iterative(root) # 输出：1 2 4 5 3
为什么根到叶的遍历重要？¶
根到叶的DFS遍历是解决“路径相关问题”的基础，例如：
- 路径求和：求所有根到叶路径的和是否等于目标值；
- 路径输出：打印所有从根到叶的路径（如示例中的1→2→4、1→2→5、1→3）；
- 最短路径：在有权树中，找到根到叶的最小/最大路径和。
总结¶
DFS（深度优先搜索）的核心是“深入一条路径，直到无法前进再回溯”。树的前序遍历是根到叶路径的典型遍历方式，递归实现简单直观，适合初学者理解；非递归实现用栈模拟递归过程，更适合处理大规模数据。掌握根到叶的DFS遍历，能帮助我们解决路径相关的算法问题，是数据结构中“树”这一章节的核心技能。