中序遍历（Inorder Traversal）
定义
中序遍历是二叉树遍历的一种方式，访问顺序为：左子树 → 根节点 → 右子树。
在递归框架中，中序位置指的是左子树都遍历完，即将开始遍历右子树的时候。
void traverse(TreeNode root) {
if (root == null) return;
traverse(root.left);
// 中序位置：左子树遍历完，即将遍历右子树
System.out.println(root.val);
traverse(root.right);
}
核心特点
- 中序位置可以获取参数数据 + 左子树的返回值
- 二叉搜索树（BST）的中序遍历结果是有序的
- 中序遍历主要用于 BST 相关场景
与 BST 的关系
对于二叉搜索树，中序遍历的结果是一个升序序列：
// BST 中序遍历 = 有序序列
void traverse(TreeNode root) {
if (root == null) return;
traverse(root.left); // 遍历左子树（所有元素 < root.val）
System.out.println(root.val); // 根节点
traverse(root.right); // 遍历右子树（所有元素 > root.val）
}
中序遍历的两种实现思路
遍历思路：
List<Integer> res = new LinkedList<>();
void traverse(TreeNode root) {
if (root == null) return;
traverse(root.left);
res.add(root.val); // 中序位置收集结果
traverse(root.right);
}
分解问题思路：
List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new LinkedList<>();
if (root == null) return res;
res.addAll(inorderTraversal(root.left));
res.add(root.val);
res.addAll(inorderTraversal(root.right));
return res;
}