力扣94题:二叉树的中序遍历(C语言实现详解)
题目描述
给定一个二叉树的根节点 root
,返回它的中序遍历(Inorder Traversal)。
中序遍历的规则是:
- 先访问左子树;
- 再访问根节点;
- 最后访问右子树。
示例 1:
输入:root = [1,null,2,3]
输出:[1,3,2]
示例 2:
输入:root = []
输出:[]
示例 3:
输入:root = [1]
输出:[1]
解题思路
-
递归方法:
使用递归函数模拟中序遍历的规则,依次访问左子树、根节点、右子树,简单直观。 -
迭代方法(栈):
使用栈显式地模拟递归过程。每次先将左子树依次压入栈中,访问到最左节点后逐步出栈,同时转向右子树。 -
Morris 遍历(优化空间):
通过线索化的方式,将树结构转换为一个遍历链表,从而实现 O ( 1 ) O(1) O(1) 额外空间的中序遍历。
方法一:递归实现
代码实现
#include <stdio.h>
#include <stdlib.h>// 定义二叉树节点结构
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;
};// 辅助函数:递归中序遍历
void inorderHelper(struct TreeNode *root, int *result, int *returnSize) {if (root == NULL) return;// 递归遍历左子树inorderHelper(root->left, result, returnSize);// 记录当前节点值result[(*returnSize)++] = root->val;// 递归遍历右子树inorderHelper(root->right, result, returnSize);
}// 主函数:返回中序遍历结果
int* inorderTraversal(struct TreeNode *root, int *returnSize) {*returnSize = 0;// 为结果数组分配空间(假设最多有 100 个节点)int *result = (int *)malloc(100 * sizeof(int));if (result == NULL) return NULL;inorderHelper(root, result, returnSize);return result;
}// 测试函数
int main() {// 构造二叉树 [1, null, 2, 3]struct TreeNode node3 = {3, NULL, NULL};struct TreeNode node2 = {2, &node3, NULL};struct TreeNode root = {1, NULL, &node2};int returnSize;int *result = inorderTraversal(&root, &returnSize);printf("中序遍历结果: ");for (int i = 0; i < returnSize; i++) {printf("%d ", result[i]);}printf("\n");free(result); // 释放内存return 0;
}
复杂度分析
-
时间复杂度:
O ( n ) O(n) O(n),其中 n n n 是二叉树的节点数,每个节点访问一次。 -
空间复杂度:
O ( h ) O(h) O(h),其中 h h h 是二叉树的高度,递归栈的最大深度为 h h h。
方法二:迭代实现
代码实现
#include <stdio.h>
#include <stdlib.h>// 定义二叉树节点结构
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;
};// 主函数:返回中序遍历结果
int* inorderTraversal(struct TreeNode *root, int *returnSize) {*returnSize = 0;int *result = (int *)malloc(100 * sizeof(int)); // 假设最多有 100 个节点if (result == NULL) return NULL;struct TreeNode *stack[100]; // 用数组模拟栈int top = -1; // 栈顶指针struct TreeNode *current = root;while (current != NULL || top != -1) {// 将所有左子节点入栈while (current != NULL) {stack[++top] = current;current = current->left;}// 弹出栈顶节点current = stack[top--];result[(*returnSize)++] = current->val;// 访问右子树current = current->right;}return result;
}// 测试函数
int main() {// 构造二叉树 [1, null, 2, 3]struct TreeNode node3 = {3, NULL, NULL};struct TreeNode node2 = {2, &node3, NULL};struct TreeNode root = {1, NULL, &node2};int returnSize;int *result = inorderTraversal(&root, &returnSize);printf("中序遍历结果: ");for (int i = 0; i < returnSize; i++) {printf("%d ", result[i]);}printf("\n");free(result); // 释放内存return 0;
}
复杂度分析
-
时间复杂度:
O ( n ) O(n) O(n),其中 n n n 是二叉树的节点数。 -
空间复杂度:
O ( h ) O(h) O(h),其中 h h h 是二叉树的高度,显式栈的最大深度为 h h h。
方法三:Morris 遍历(优化空间)
代码实现
#include <stdio.h>
#include <stdlib.h>// 定义二叉树节点结构
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;
};// 主函数:返回中序遍历结果
int* inorderTraversal(struct TreeNode *root, int *returnSize) {*returnSize = 0;int *result = (int *)malloc(100 * sizeof(int)); // 假设最多有 100 个节点if (result == NULL) return NULL;struct TreeNode *current = root, *pre;while (current != NULL) {if (current->left == NULL) {result[(*returnSize)++] = current->val;current = current->right;} else {pre = current->left;while (pre->right != NULL && pre->right != current) {pre = pre->right;}if (pre->right == NULL) {pre->right = current;current = current->left;} else {pre->right = NULL;result[(*returnSize)++] = current->val;current = current->right;}}}return result;
}// 测试函数
int main() {// 构造二叉树 [1, null, 2, 3]struct TreeNode node3 = {3, NULL, NULL};struct TreeNode node2 = {2, &node3, NULL};struct TreeNode root = {1, NULL, &node2};int returnSize;int *result = inorderTraversal(&root, &returnSize);printf("中序遍历结果: ");for (int i = 0; i < returnSize; i++) {printf("%d ", result[i]);}printf("\n");free(result); // 释放内存return 0;
}
复杂度分析
-
时间复杂度:
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 遍历适合对空间要求极高的情况。