给定一个二叉树的根节点 root ，返回 它的 中序**遍历 。
示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
提示：
- 树中节点数目在范围
[0, 100]内 -100 <= Node.val <= 100
还是靠递归解出题来
1. 算法核心思想：递归与中序原则
二叉树的中序遍历有着极其严格的顺序规则：左子树 -> 根节点 -> 右子树。 对于这种具有“自相似结构”的树形问题，递归是第一直觉解法。我们将遍历的过程拆解给辅助函数 nodeseek，它的任务非常单一：
- 先看看左边有没有人，有的话就让左边的人先报数（递归左子树）。
- 然后自己报数（将当前节点的值
push_back到结果数组中）。 - 最后看看右边有没有人，有的话让右边的人报数（递归右子树）。
2. 逻辑亮点：引用传递消除副作用
本题如果将结果数组放在类变量（全局变量）中，虽然能解决问题，但会破坏函数的封装性，导致多次调用互相污染。 本解法采用在主函数中初始化 result，并通过 vector<int>& result (引用传递) 的方式送入递归函数。这种做法保证了无论递归深入到哪一层，大家都在往同一个物理内存中的 result 里追加数据，既省去了疯狂拷贝数组的巨大性能开销，又保持了代码的优雅和局部性。
class Solution {
public:
// 主函数
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
// 边界处理：空树直接返回空数组
if (root == NULL) {
return result;
}
// 调用递归寻找节点，注意这里把 result 的本体传了进去
nodeseek(result, root);
return result;
}
// 辅助递归函数：中序遍历核心逻辑
// 这里的 & 极其关键：表示 result 是引用传递，所有递归共享同一个数组
void nodeseek(vector<int>& result, TreeNode* node) {
// 1. 遍历左子树
if (node->left != NULL) {
nodeseek(result, node->left);
}
// 2. 记录当前根节点的值
result.push_back(node->val);
// 3. 遍历右子树
if (node->right != NULL) {
nodeseek(result, node->right);
}
}
};
3. 复杂度分析
- 时间复杂度：O(N)。其中 N 是二叉树的节点数。因为每个节点都会被严格地访问且仅访问一次。
- 空间复杂度：O(H)。其中 H 是二叉树的高度。空间消耗主要来自于递归调用时系统分配的函数调用栈深度。在最坏情况下（树退化成一条链），高度 H=N，空间复杂度为 O(N)；在最好情况下（完全二叉树），高度 H=logN，空间复杂度为 O(logN)。这里不把存储返回结果的
result数组计入额外的空间复杂度计算中。