我的二叉树中序遍历解题思路（C++递归实现）

我的二叉树中序遍历解题思路（C++递归实现）

在刷LeetCode 94题「二叉树的中序遍历」时，我采用了简洁直观的递归写法，核心思路围绕中序遍历「左子树→根节点→右子树」的核心顺序展开。本文将详细讲解我的代码逻辑、执行流程及优化方向，适合作为个人学习笔记或博客分享。

一、题目回顾

题目要求

给定二叉树的根节点 root ，返回其中序遍历的节点值列表。

- 树中节点数目范围： [0, 100]
- 节点值范围： [-100, 100]

示例

输入： root = [1,null,2,3] ，输出： [1,3,2] （遍历顺序：1的左子树→1→2的左子树（3）→3→2→2的右子树）

二、我的代码实现

cpp

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> result; // 存储遍历结果的全局变量
vector<int> inorderTraversal(TreeNode* root) {
if(root == NULL){ // 终止条件：当前节点为空，直接返回结果
return result;
}
inorderTraversal(root->left); // 1. 递归遍历左子树
result.push_back(root->val); // 2. 访问当前根节点，加入结果集
inorderTraversal(root->right); // 3. 递归遍历右子树
return result;
}
};


三、代码逻辑详解

1. 核心思路

递归的本质是利用系统调用栈自动维护遍历顺序，无需手动管理栈结构，完全贴合中序遍历的逻辑：

- 先深入左子树的最底层（直到节点为空）；
- 回溯时访问当前根节点（将值存入结果集）；
- 最后递归遍历右子树，重复上述过程。

2. 关键部分解析

（1）全局变量 result

- 作用：存储遍历后的节点值，避免每次递归时重新创建向量（减少拷贝开销）。
- 注意：若多次调用 inorderTraversal 函数，需在每次调用前清空 result （但本题为单次调用，无需处理）。

（2）终止条件 if(root == NULL)

- 当递归到空节点时（左子树或右子树遍历完毕），直接返回当前结果集，避免空指针访问错误。

（3）递归流程

1. inorderTraversal(root->left) ：优先遍历左子树，直到触发终止条件；
2. result.push_back(root->val) ：左子树遍历完成后，访问当前根节点，将值加入结果集；
3. inorderTraversal(root->right) ：遍历当前节点的右子树，重复「左→根→右」流程。

3. 执行流程演示（以示例1为例）

输入： root = [1,null,2,3] （二叉树结构如下）

plaintext

1
\
2
/
3


执行步骤：

1. 调用 inorderTraversal(1) → 先执行 inorderTraversal(1->left) （1的左子树为空，返回空结果集）；
2. 将1的值加入 result ，此时 result = [1] ；
3. 调用 inorderTraversal(1->right) （即节点2）；
4. 调用 inorderTraversal(2->left) （即节点3）；
5. 调用 inorderTraversal(3->left) （3的左子树为空，返回）；
6. 将3的值加入 result ，此时 result = [1,3] ；
7. 调用 inorderTraversal(3->right) （3的右子树为空，返回）；
8. 回到节点2，将2的值加入 result ，此时 result = [1,3,2] ；
9. 调用 inorderTraversal(2->right) （2的右子树为空，返回）；
10. 遍历结束，返回 result = [1,3,2] 。

四、代码优缺点分析

优点

1. 简洁直观：代码仅需几行核心逻辑，完全贴合中序遍历的定义，易写易理解；
2. 无额外空间开销：无需手动维护栈，依赖系统栈，代码简洁度高；
3. 适配题目约束：本题节点数≤100，递归深度不会触发栈溢出，完全适用。

缺点

1. 递归深度限制：若二叉树为斜树（如链状，深度=10^4），会触发栈溢出（C++默认递归栈深度约为1e4）；
2. 全局变量风险：若函数被多次调用， result 中的旧数据会影响新结果（需手动清空）；
3. 可读性依赖递归理解：对递归不熟悉的开发者可能难以追踪执行流程。

五、优化方向（可选拓展）

1. 避免全局变量：使用局部变量+辅助函数

将 result 改为局部变量，通过辅助函数传递引用，避免全局变量的副作用：

cpp

class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result; // 局部变量
dfs(root, result); // 辅助函数，传递引用
return result;
}
private:
// 辅助递归函数：遍历以node为根的子树，结果存入res
void dfs(TreeNode* node, vector<int>& res) {
if (node == nullptr) return;
dfs(node->left, res);
res.push_back(node->val);
dfs(node->right, res);
}
};


优势：每次调用 inorderTraversal 都会创建新的 result ，避免多次调用时的数据污染，更符合函数设计规范。

2. 迭代实现（解决栈溢出问题）

若需处理大规模二叉树，可手动模拟栈实现迭代遍历，避免递归栈溢出：

cpp

#include <stack>
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> stk;
TreeNode* cur = root;
while (cur != nullptr || !stk.empty()) {
// 所有左子节点入栈
while (cur != nullptr) {
stk.push(cur);
cur = cur->left;
}
// 出栈访问根节点
cur = stk.top();
stk.pop();
result.push_back(cur->val);
// 遍历右子树
cur = cur->right;
}
return result;
}
};


优势：空间复杂度仍为 O(h)（h为树的高度），但无递归深度限制，适用于任意规模的二叉树。

六、注意事项

1. 空树处理：当 root = nullptr 时，函数直接返回空的 result ，无需额外判断；
2. 节点值范围：题目中节点值可能为负数（-100≤val≤100）， push_back 可直接处理，无需特殊逻辑；
3. 递归栈溢出：本题节点数≤100，递归版本完全安全；若题目无节点数限制，优先选择迭代版本或Morris遍历（空间复杂度O(1)）。

七、总结

我的解法以递归为核心，充分利用系统栈简化代码，完美贴合中序遍历的「左→根→右」逻辑，适合入门理解和小规模场景。若需优化，可通过「局部变量+辅助函数」解决全局变量问题，或用迭代法处理大规模二叉树。

中序遍历是二叉树的基础遍历方式，尤其在二叉搜索树中能获取升序序列，掌握递归与迭代两种实现，能轻松应对各类相关题目。如果有其他优化思路或疑问，欢迎在评论区交流！



博客拓展建议

1. 可添加递归调用栈的示意图，直观展示每次递归的入栈、出栈过程；
2. 补充Morris遍历的实现（空间复杂度O(1)），提升博客深度；
3. 对比前序、中序、后序遍历的递归写法差异，帮助读者举一反三。