94. 二叉树的中序遍历
3 min
题目
解法：递归遍历
思路
核心思想是递归地按照’左子树→根节点→右子树’的顺序访问每个节点。
该方法正确性基于中序遍历的定义：对于任意节点，先遍历其左子树，再访问根节点，最后遍历右子树。递归确保了每个子树都遵循相同规则，且每个节点恰好被访问一次，从而得到正确的中序序列。
- Step 1: 定义辅助递归函数 helper，接收当前节点和结果数组引用
- Step 2: 如果当前节点为空，直接返回
- Step 3: 递归调用 helper 遍历左子树
- Step 4: 将当前节点的值加入结果数组
- Step 5: 递归调用 helper 遍历右子树
复杂度
- 时间复杂度: ，其中 n 为节点数，每个节点仅被访问一次。
- 空间复杂度: ，结果数组存储 n 个元素，递归栈空间最坏情况下为 O(n)。
代码
/**
* 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> inorderTraversal(TreeNode* root) {
vector<int> ans;
helper(root, ans);
return ans;
}
private:
void helper(TreeNode* node, vector<int>& res) {
if (node == nullptr) return;
helper(node->left, res);
res.push_back(node->val);
/**
* 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> inorderTraversal(TreeNode* root) {
vector<int> ans;
helper(root, ans);
return ans;
}
private:
void helper(TreeNode* node, vector<int>& res) {
if (node == nullptr) return;
helper(node->left, res);
res.push_back(node->val);
helper(node->right, res);
}
};