前序遍历（Preorder Traversal）
定义
前序遍历是二叉树遍历的一种方式，访问顺序为：根节点 → 左子树 → 右子树。
在递归框架中，前序位置指的是刚进入一个二叉树节点的时候（递归调用之前）。
void traverse(TreeNode root) {
if (root == null) return;
// 前序位置：刚进入节点
System.out.println(root.val);
traverse(root.left);
traverse(root.right);
}
核心特点
- 前序位置是进入节点的时候，此时只能从函数参数中获取父节点传递来的数据
- 前序位置适合做「选择」：类比 DFS 算法，做选择的逻辑放在 for 循环外面
- 快速排序的本质就是二叉树的前序遍历
与算法框架的联系
快速排序 = 前序遍历
void sort(int[] nums, int lo, int hi) {
if (lo >= hi) return;
// 前序位置：构造分界点
int p = partition(nums, lo, hi);
sort(nums, lo, p - 1);
sort(nums, p + 1, hi);
}
前序遍历的两种实现思路
遍历思路（常规，用外部变量）：
List<Integer> res = new LinkedList<>();
void traverse(TreeNode root) {
if (root == null) return;
res.add(root.val); // 前序位置收集结果
traverse(root.left);
traverse(root.right);
}
分解问题思路（函数返回值）：
List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new LinkedList<>();
if (root == null) return res;
res.add(root.val);
res.addAll(preorderTraversal(root.left));
res.addAll(preorderTraversal(root.right));
return res;
}