题目描述

给定一个二叉树的根节点 root，返回它的 中序遍历 结果。

示例

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

提示

• 树中节点数目在范围 [0, 100] 内
• -100 <= Node.val <= 100

---

方法 1：递归法

思路

中序遍历的顺序为：左子树 → 根节点 → 右子树。

代码实现

#include <stdlib.h>struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;
};void inorder(struct TreeNode* root, int* result, int* returnSize) {if (!root) {return;}inorder(root->left, result, returnSize);result[(*returnSize)++] = root->val;inorder(root->right, result, returnSize);
}int* inorderTraversal(struct TreeNode* root, int* returnSize) {int* result = (int*)malloc(501 * sizeof(int)); // 预分配足够的空间*returnSize = 0;inorder(root, result, returnSize);return result;
}

复杂度分析

• 时间复杂度：O(n)，每个节点访问一次。
• 空间复杂度：O(n)，最坏情况下（单链表形式的树），递归调用栈深度为 O(n)。

---

方法 2：迭代法（栈模拟）

思路

使用栈来模拟递归过程：

1. 先沿着左子树一路入栈，直到最左叶子。
2. 弹出栈顶元素，访问该节点。
3. 转向右子树，继续步骤 1 和 2。

代码实现

#include <stdlib.h>int* inorderTraversal(struct TreeNode* root, int* returnSize) {int* result = (int*)malloc(501 * sizeof(int));*returnSize = 0;struct TreeNode** stack = (struct TreeNode**)malloc(501 * sizeof(struct TreeNode*));int top = 0;while (root || top) {while (root) {stack[top++] = root;root = root->left;}root = stack[--top]; // 出栈访问result[(*returnSize)++] = root->val;root = root->right;}free(stack);return result;
}

复杂度分析

• 时间复杂度：O(n)，每个节点入栈和出栈各一次。
• 空间复杂度：O(n)，最坏情况下栈深度为 O(n)。

---

方法 3：Morris 遍历（线索化二叉树）

思路

Morris 遍历通过线索二叉树来减少空间复杂度，步骤如下：

1. 如果当前节点没有左子树，访问该节点并进入右子树。
2. 如果当前节点有左子树，找到前驱节点（左子树的最右节点）：
   • 若前驱节点的 right 为空，将其 right 指向当前节点，然后进入左子树。
   • 若前驱节点的 right 为当前节点，说明左子树已访问，访问当前节点，恢复前驱节点的 right 指针为空，然后进入右子树。

代码实现

#include <stdlib.h>int* inorderTraversal(struct TreeNode* root, int* returnSize) {int* result = (int*)malloc(501 * sizeof(int));*returnSize = 0;struct TreeNode* predecessor = NULL;while (root) {if (root->left) {predecessor = root->left;while (predecessor->right && predecessor->right != root) {predecessor = predecessor->right;}if (!predecessor->right) {predecessor->right = root;root = root->left;} else {result[(*returnSize)++] = root->val;predecessor->right = NULL;root = root->right;}} else {result[(*returnSize)++] = root->val;root = root->right;}}return result;
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/binary-tree-inorder-traversal/solutions/412886/er-cha-shu-de-zhong-xu-bian-li-by-leetcode-solutio/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复杂度分析

• 时间复杂度：O(n)，每个节点访问最多两次。
• 空间复杂度：O(1)，仅使用了额外的指针变量。

---

三种方法对比

方法	时间复杂度	空间复杂度	适用场景
递归	O(n)	O(n)	代码简洁，适合初学者
迭代（栈）	O(n)	O(n)	适用于系统栈深度受限的情况
Morris	O(n)	O(1)	适用于对空间复杂度有严格要求的情况

---

总结

1. 递归法 是最直观的方法，但会消耗额外的栈空间。
2. 迭代法（栈模拟） 通过显式栈实现递归过程，适用于深度受限的情况。
3. Morris 遍历法 通过修改树结构实现 O(1) 空间复杂度，是一种高效方法，但对原树结构有一定影响。