LeetCode题解--94.二叉树的中序遍历（简单）

一，题目描述

二，解题思路

中序遍历的顺序是：左子树 → 根节点 → 右子树。我们可以通过三种方法实现：递归、迭代（栈）和 Morris 遍历。
方法 1：递归
递归是最直观的方法，按照中序遍历的顺序递归访问左子树、根节点、右子树。
复杂度分析：
时间复杂度：O (n)，每个节点恰好访问一次。
空间复杂度：O (n)，最坏情况下（树退化为链表），递归栈需要 O (n) 空间。
方法 2：迭代（栈）
用栈模拟递归过程，先将所有左子节点入栈，然后出栈访问根节点，再处理右子树。
复杂度分析：
时间复杂度：O (n)，每个节点入栈和出栈各一次。
空间复杂度：O (n)，栈最多存储 n 个节点。
方法 3：Morris 遍历（空间优化）
利用线索二叉树的思想，无需额外栈空间，通过修改树的结构来记录遍历顺序。
复杂度分析：
时间复杂度：O (n)，每个节点访问两次（建立线索和访问节点）。
空间复杂度：O (1)，只使用常数额外空间。

三，代码实现

1. 递归实现

// 二叉树节点定义 struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; }; // 递归辅助函数 void inorder(struct TreeNode* root, int* res, int* returnSize) { if (root == NULL) return; inorder(root->left, res, returnSize); // 遍历左子树 res[(*returnSize)++] = root->val; // 访问根节点 inorder(root->right, res, returnSize); // 遍历右子树 } // 主函数 int* inorderTraversal(struct TreeNode* root, int* returnSize) { *returnSize = 0; int* res = (int*)malloc(sizeof(int) * 100); // 题目提示节点数≤100 inorder(root, res, returnSize); return res; }

参数解析

关键逻辑拆解

①递归终止条件：if (root == NULL) return;

• 当遍历到 “空节点”（比如叶子节点的左 / 右指针），说明当前分支遍历完毕，触发回溯，回到上一层递归。

②中序遍历核心顺序：

• inorder(root->left, ...)：先把左子树 “挖到底”，直到左子节点为 NULL，才会执行后续代码。
• res[(*returnSize)++] = root->val：这是中序遍历的 “核心操作”—— 访问当前节点值，存入结果数组。
  • 重点解释(*returnSize)++：
    • returnSize是指针，*returnSize是解引用，拿到它指向的 “数组长度值”（比如初始为 0）。
    • 先以*returnSize作为数组索引（比如初始时res[0]），将当前节点值存入数组；
    • 再执行++，让长度值自增（比如 0→1），为下一个节点的存储预留索引。
    • ❌ 错误写法：returnSize++（仅修改指针地址，不会改变数组长度值）。
• inorder(root->right, ...)：左子树和当前节点处理完后，递归处理右子树。

• int* inorderTraversal(struct TreeNode* root, int* returnSize) { *returnSize = 0; // 初始化结果数组长度为0（遍历前无元素） // 分配结果数组的内存：int类型数组，长度100（题目提示节点数≤100） int* res = (int*)malloc(sizeof(int) * 100); inorder(root, res, returnSize); // 调用递归函数，填充结果数组 return res; // 返回结果数组的首地址（堆内存） }

  关键逻辑拆解
  ① 初始化长度：*returnSize = 0;
  必须先初始化！否则returnSize指向的内存值是随机的，会导致res[随机数]赋值时数组越界 / 数据错乱。
  ② 内存分配：int* res = (int*)malloc(sizeof(int) * 100);
  malloc：在堆内存分配连续空间（栈内存函数结束后会释放，无法返回），返回空间首地址。
  sizeof(int) * 100：每个int占 4 字节（32 位系统），100 个元素共 400 字节，足够存储题目要求的所有节点值。
  注意：调用者使用完res后，需要用free(res)释放内存，避免内存泄漏。
  ③ 调用递归函数：inorder(root, res, returnSize);
  把根节点、结果数组、长度指针传给辅助函数，递归填充数组。
  ④ 返回结果：return res;
  返回堆内存数组的首地址，调用者可以通过这个指针访问遍历结果（比如res[0]是第一个遍历值）。

2.栈实现

int* inorderTraversal(struct TreeNode* root, int* returnSize) { *returnSize = 0; int* res = (int*)malloc(sizeof(int) * 100); struct TreeNode** stack = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * 100); int top = -1; // 栈顶指针 struct TreeNode* curr = root; while (curr != NULL || top != -1) { // 遍历所有左子节点，入栈 while (curr != NULL) { stack[++top] = curr; curr = curr->left; } // 出栈访问根节点 curr = stack[top--]; res[(*returnSize)++] = curr->val; // 处理右子树 curr = curr->right; } free(stack); return res; }

1.关键变量解释：
stack：二级指针（TreeNode**）→ 本质是「存储节点指针的数组」，数组里每个元素是TreeNode*（指向二叉树节点的指针），stack指向这个数组的首地址，因此是 “指针的指针”。
top：栈顶索引，规则是：
top=-1 → 空栈；
stack[++top] → 入栈（先把 top+1，再存值）；
stack[top--] → 出栈（先取值，再把 top-1）。
curr：跟踪当前正在处理的节点，替代递归中 “当前层的根节点”。
2.核心循环逻辑（中序遍历的核心）
外层while是迭代的总入口，条件curr != NULL || top != -1：
只要「当前节点非空」（还有左子节点要处理）或「栈非空」（还有待访问的节点），就继续遍历（避免遗漏右子树或未访问的节点）。

步骤 1：内层 while → 遍历所有左子节点，依次入栈

while (curr != NULL) { stack[++top] = curr; // 入栈：当前节点压入栈，top+1 curr = curr->left; // 移动到左子节点，继续找下一个左子节点 }

• 作用：模拟递归中 “先遍历左子树到底” 的过程，把当前节点 + 所有左子节点依次压栈，直到curr为 NULL（左子树遍历完毕）。
• 举例：若节点有左子树，会一直往左走，每走一步就把节点压栈，确保栈顶是「最左侧的节点」（中序遍历第一个要访问的节点）。

步骤 2：出栈并访问根节点

curr = stack[top--]; // 出栈：取出栈顶节点，top-1（栈顶下移） res[(*returnSize)++] = curr->val; // 访问节点值：存入结果数组，长度+1

• 作用：左子树处理完后，栈顶就是 “当前要访问的根节点”，取出并将值存入结果数组。
• 关键：(*returnSize)++→ 先解引用returnSize拿到当前长度（作为数组索引），存入值后长度自增，确保下一个值存在正确位置（若直接写returnSize++，仅修改指针地址，不会改变长度值）。

步骤 3：处理右子树

curr = curr->right; // 移动到当前节点的右子节点

• 作用：根节点访问完后，按中序遍历规则处理右子树 —— 此时curr指向右子节点，外层循环会重复「压左子节点→出栈访问→处理右子树」的逻辑，完成右子树的遍历。

4. 内存管理

free(stack); // 释放手动分配的栈空间，避免内存泄漏 return res; // 返回结果数组（调用者需手动free(res)）

• stack是函数内分配的堆内存，函数结束前必须释放；
• res是返回给调用者的结果数组，调用者使用完后需调用free(res)释放，否则会内存泄漏。

3. Morris 遍历

int* inorderTraversal(struct TreeNode* root, int* returnSize) { *returnSize = 0; int* res = (int*)malloc(sizeof(int) * 100); struct TreeNode* curr = root; struct TreeNode* pre; while (curr != NULL) { if (curr->left == NULL) { // 左子树为空，访问根节点，转向右子树 res[(*returnSize)++] = curr->val; curr = curr->right; } else { // 找到左子树的最右节点（前驱节点） pre = curr->left; while (pre->right != NULL && pre->right != curr) { pre = pre->right; } if (pre->right == NULL) { // 建立线索，指向当前节点 pre->right = curr; curr = curr->left; } else { // 线索已存在，访问当前节点，恢复树结构 pre->right = NULL; res[(*returnSize)++] = curr->val; curr = curr->right; } } } return res; }

1.变量定义与初始化

*returnSize = 0; // 初始化结果数组长度为0，避免随机值导致索引错误 // 分配结果数组：int类型，长度100（题目限制节点数≤100），堆内存存储 int* res = (int*)malloc(sizeof(int) * 100); struct TreeNode* curr = root; // 当前遍历的节点指针，初始指向根节点 struct TreeNode* pre; // 用于找「当前节点的中序前驱节点」（左子树最右节点）

关键概念：中序前驱节点对当前节点curr来说，其中序遍历的前驱节点是「左子树的最右侧节点」—— 中序遍历中，这个节点是curr的前一个被访问节点，Morris 遍历通过把前驱节点的right指针指向curr，建立 “线索”，避免用栈记录回溯路径。

2. 核心循环逻辑（Morris 遍历的核心）

外层while (curr != NULL)：只要当前节点非空，就继续遍历（Morris 遍历无栈，仅通过节点指针移动完成）。

分支 1：当前节点的左子树为空（curr->left == NULL）

if (curr->left == NULL) { // 左子树为空，直接访问当前节点（中序遍历：左空则根是第一个访问的） res[(*returnSize)++] = curr->val; // 转向右子树（无左子树，处理完根就处理右） curr = curr->right; }

• 逻辑：左子树为空时，当前节点是中序遍历的 “当前待访问节点”，存入结果数组后，直接移动到右子节点继续遍历。
• 举例：叶子节点（左右子树都空）会执行这一分支，访问后curr变为 NULL，循环结束。

分支 2：当前节点的左子树非空（curr->left != NULL）

else { // 步骤1：找到curr左子树的最右侧节点（即curr的中序前驱节点pre） pre = curr->left; while (pre->right != NULL && pre->right != curr) { pre = pre->right; } // 子分支1：前驱节点的right为空 → 建立线索 if (pre->right == NULL) { pre->right = curr; // 把pre的right指向curr，建立“回溯线索” curr = curr->left; // 移动到左子节点，继续处理左子树 } // 子分支2：前驱节点的right指向curr → 线索已存在，恢复树结构+访问节点 else { pre->right = NULL; // 恢复pre的right为NULL（还原树的原始结构） res[(*returnSize)++] = curr->val; // 访问当前节点（左子树已遍历完） curr = curr->right; // 转向右子树 } }

步骤拆解（左子树非空时的核心逻辑）：

①找前驱节点：pre从curr->left出发，一直往右走（pre = pre->right），直到pre->right为 NULL（没建立线索）或pre->right == curr（已建立线索）—— 这一步是为了找到curr的中序前驱节点。

②第一次访问前驱节点（pre->right == NULL）：

• 此时左子树还未遍历，需要先建立 “回溯线索”：把pre->right指向curr（这样遍历完左子树后，能通过这个线索回到curr）；
• 然后curr移动到左子节点（curr = curr->left），继续处理左子树（重复整个循环）。

③第二次访问前驱节点（pre->right == curr）：

• 此时说明curr的左子树已经遍历完毕（因为能通过线索回到curr），需要先恢复树的原始结构（把pre->right置为 NULL，避免修改原树）；
• 然后访问curr节点（存入结果数组），再移动到右子节点（curr = curr->right）处理右子树。