力扣94题：二叉树的中序遍历

力扣94题：二叉树的中序遍历（C语言实现详解）

题目形貌

给定一个二叉树的根节点 root ，返回它的中序遍历（Inorder Traversal）。
中序遍历的规则是：

• 先访问左子树；
  
• 再访问根节点；
  
• 末了访问右子树。
  

示例 1：

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

复制代码

示例 2：

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

复制代码

示例 3：

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

复制代码

---

解题思绪

• 递归方法：
  利用递归函数模拟中序遍历的规则，依次访问左子树、根节点、右子树，简单直观。
  
• 迭代方法（栈）：
  利用栈显式地模拟递归过程。每次先将左子树依次压入栈中，访问到最左节点后逐步出栈，同时转向右子树。
  
• Morris 遍历（优化空间）：
  通过线索化的方式，将树布局转换为一个遍历链表，从而实现                                              O                               (                               1                               )                                      O(1)                        O(1) 额外空间的中序遍历。
  

---

方法一：递归实现

代码实现

1. #include <stdio.h>
2. #include <stdlib.h>
4. // 定义二叉树节点结构
5. struct TreeNode {
6.     int val;
7.     struct TreeNode *left;
8.     struct TreeNode *right;
9. };
11. // 辅助函数：递归中序遍历
12. void inorderHelper(struct TreeNode *root, int *result, int *returnSize) {
13.     if (root == NULL) return;
15.     // 递归遍历左子树
16.     inorderHelper(root->left, result, returnSize);
17.     // 记录当前节点值
18.     result[(*returnSize)++] = root->val;
19.     // 递归遍历右子树
20.     inorderHelper(root->right, result, returnSize);
21. }
23. // 主函数：返回中序遍历结果
24. int* inorderTraversal(struct TreeNode *root, int *returnSize) {
25.     *returnSize = 0;
27.     // 为结果数组分配空间（假设最多有 100 个节点）
28.     int *result = (int *)malloc(100 * sizeof(int));
29.     if (result == NULL) return NULL;
31.     inorderHelper(root, result, returnSize);
32.     return result;
33. }
35. // 测试函数
36. int main() {
37.     // 构造二叉树 [1, null, 2, 3]
38.     struct TreeNode node3 = {3, NULL, NULL};
39.     struct TreeNode node2 = {2, &node3, NULL};
40.     struct TreeNode root = {1, NULL, &node2};
42.     int returnSize;
43.     int *result = inorderTraversal(&root, &returnSize);
45.     printf("中序遍历结果: ");
46.     for (int i = 0; i < returnSize; i++) {
47.         printf("%d ", result[i]);
48.     }
49.     printf("\n");
51.     free(result); // 释放内存
52.     return 0;
53. }

复制代码

---

复杂度分析

• 时间复杂度：
                                                O                               (                               n                               )                                      O(n)                        O(n)，其中                                              n                                      n                        n 是二叉树的节点数，每个节点访问一次。
  
• 空间复杂度：
                                                O                               (                               h                               )                                      O(h)                        O(h)，其中                                              h                                      h                        h 是二叉树的高度，递归栈的最大深度为                                              h                                      h                        h。
  

---

方法二：迭代实现

代码实现

1. #include <stdio.h>
2. #include <stdlib.h>
4. // 定义二叉树节点结构
5. struct TreeNode {
6.     int val;
7.     struct TreeNode *left;
8.     struct TreeNode *right;
9. };
11. // 主函数：返回中序遍历结果
12. int* inorderTraversal(struct TreeNode *root, int *returnSize) {
13.     *returnSize = 0;
14.     int *result = (int *)malloc(100 * sizeof(int)); // 假设最多有 100 个节点
15.     if (result == NULL) return NULL;
17.     struct TreeNode *stack[100]; // 用数组模拟栈
18.     int top = -1; // 栈顶指针
19.     struct TreeNode *current = root;
21.     while (current != NULL || top != -1) {
22.         // 将所有左子节点入栈
23.         while (current != NULL) {
24.             stack[++top] = current;
25.             current = current->left;
26.         }
28.         // 弹出栈顶节点
29.         current = stack[top--];
30.         result[(*returnSize)++] = current->val;
32.         // 访问右子树
33.         current = current->right;
34.     }
36.     return result;
37. }
39. // 测试函数
40. int main() {
41.     // 构造二叉树 [1, null, 2, 3]
42.     struct TreeNode node3 = {3, NULL, NULL};
43.     struct TreeNode node2 = {2, &node3, NULL};
44.     struct TreeNode root = {1, NULL, &node2};
46.     int returnSize;
47.     int *result = inorderTraversal(&root, &returnSize);
49.     printf("中序遍历结果: ");
50.     for (int i = 0; i < returnSize; i++) {
51.         printf("%d ", result[i]);
52.     }
53.     printf("\n");
55.     free(result); // 释放内存
56.     return 0;
57. }

复制代码

---

复杂度分析

• 时间复杂度：
                                                O                               (                               n                               )                                      O(n)                        O(n)，其中                                              n                                      n                        n 是二叉树的节点数。
  
• 空间复杂度：
                                                O                               (                               h                               )                                      O(h)                        O(h)，其中                                              h                                      h                        h 是二叉树的高度，显式栈的最大深度为                                              h                                      h                        h。
  

---

方法三：Morris 遍历（优化空间）

代码实现

1. #include <stdio.h>
2. #include <stdlib.h>
4. // 定义二叉树节点结构
5. struct TreeNode {
6.     int val;
7.     struct TreeNode *left;
8.     struct TreeNode *right;
9. };
11. // 主函数：返回中序遍历结果
12. int* inorderTraversal(struct TreeNode *root, int *returnSize) {
13.     *returnSize = 0;
14.     int *result = (int *)malloc(100 * sizeof(int)); // 假设最多有 100 个节点
15.     if (result == NULL) return NULL;
17.     struct TreeNode *current = root, *pre;
19.     while (current != NULL) {
20.         if (current->left == NULL) {
21.             result[(*returnSize)++] = current->val;
22.             current = current->right;
23.         } else {
24.             pre = current->left;
25.             while (pre->right != NULL && pre->right != current) {
26.                 pre = pre->right;
27.             }
29.             if (pre->right == NULL) {
30.                 pre->right = current;
31.                 current = current->left;
32.             } else {
33.                 pre->right = NULL;
34.                 result[(*returnSize)++] = current->val;
35.                 current = current->right;
36.             }
37.         }
38.     }
40.     return result;
41. }
43. // 测试函数
44. int main() {
45.     // 构造二叉树 [1, null, 2, 3]
46.     struct TreeNode node3 = {3, NULL, NULL};
47.     struct TreeNode node2 = {2, &node3, NULL};
48.     struct TreeNode root = {1, NULL, &node2};
50.     int returnSize;
51.     int *result = inorderTraversal(&root, &returnSize);
53.     printf("中序遍历结果: ");
54.     for (int i = 0; i < returnSize; i++) {
55.         printf("%d ", result[i]);
56.     }
57.     printf("\n");
59.     free(result); // 释放内存
60.     return 0;
61. }

复制代码

---

复杂度分析

• 时间复杂度：
                                                O                               (                               n                               )                                      O(n)                        O(n)，每个节点访问两次。
  
• 空间复杂度：
                                                O                               (                               1                               )                                      O(1)                        O(1)，无需额外栈空间。
  

---

总结

方法时间复杂度空间复杂度特点递归                                                  O                                  (                                  n                                  )                                          O(n)                           O(n)                                                  O                                  (                                  h                                  )                                          O(h)                           O(h)简单易实现，但依赖递归栈。迭代（栈）                                                  O                                  (                                  n                                  )                                          O(n)                           O(n)                                                  O                                  (                                  h                                  )                                          O(h)                           O(h)显式利用栈，得当较大的二叉树。Morris 遍历                                                  O                                  (                                  n                                  )                                          O(n)                           O(n)                                                  O                                  (                                  1                                  )                                          O(1)                           O(1)无额外空间需求，但实现较复杂。 不同方法得当不同场景，推荐优先利用递归和迭代方法，Morris 遍历得当对空间要求极高的情况。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。