94. 二叉树的中序遍历 c

### 关于二叉树中序遍历的C语言实现 在二叉树的遍历过程中，存在多种方法可以完成这一操作。其中最常见的两种方式分别为递归法和迭代法[^1]。 #### 递归法实现 递归法是一种直观且易于理解的方式用于实现二叉树的中序遍历。以下是基于C语言的具体代码示例： ```c void BTreeInOrder(struct TreeNode* root, int* arry, int* returnSize) { if (NULL == root) { // 判断当前节点是否为空 return; } BTreeInOrder(root->left, arry, returnSize); // 遍历左子树 arry[(*returnSize)++] = root->val; // 访问根节点并存储其值 BTreeInOrder(root->right, arry, returnSize); // 遍历右子树 } ``` 上述代码通过递归调用实现了对二叉树的中序遍历，并将访问到的节点值依次存入`arry`数组中[^2]。 --- #### 迭代法实现 相较于递归法，迭代法则利用显式的栈结构模拟函数调用的过程。这种方法能够有效避免因递归过深而导致的堆栈溢出问题。具体实现如下所示： ```c #include <stdlib.h> typedef struct StackNode { struct TreeNode* data; struct StackNode* next; } StackNode; StackNode* createStackNode(struct TreeNode* treeNode) { StackNode* newNode = malloc(sizeof(StackNode)); newNode->data = treeNode; newNode->next = NULL; return newNode; } int* inorderTraversal(struct TreeNode* root, int* returnSize) { *returnSize = 0; int* result = malloc(100 * sizeof(int)); // 假设最多有100个节点 StackNode* stackTop = NULL; while (root != NULL || stackTop != NULL) { // 不断向左深入直到叶子结点 while (root != NULL) { StackNode* temp = createStackNode(root); temp->next = stackTop; stackTop = temp; root = root->left; } // 出栈处理 if (stackTop != NULL) { root = stackTop->data; free(stackTop); stackTop = stackTop->next; result[*returnSize] = root->val; (*returnSize)++; // 转向右子树继续遍历 root = root->right; } } return result; } ``` 此段代码展示了如何借助栈数据结构来逐步访问每一个节点，从而完成整个二叉树的中序遍历过程[^3]。 --- #### 数据规模约束 需要注意的是，在实际应用中应考虑输入数据的大小范围以及可能存在的极端情况。例如题目描述中的提示表明：树中节点数量位于区间 `[0, 100]` 内，而节点值则满足 `-100 <= Node.val <= 100` 的条件[^4]。 ---