题目名称：二叉树的中序遍历

题目叙述：

给定一个二叉树的根节点 root，返回它的中序遍历结果。中序遍历是指先遍历左子树，然后访问根节点，最后遍历右子树。

例如，对于二叉树：

    1
     \
      2
     /
    3

中序遍历结果为 [1,3,2]。

模式识别（考点）：

• 树的遍历：主要考查对二叉树的中序遍历的理解和实现。
• 递归和迭代的应用：可以使用递归或迭代的方法来解决该问题。
• 栈的使用：在迭代方法中，需要使用栈来辅助存储节点信息。

解题方法过程：

• 方法一：递归法：

  1. 若当前节点不为空，递归调用中序遍历函数对左子树进行遍历。
  2. 访问当前节点，将当前节点的值添加到结果列表中。
  3. 递归调用中序遍历函数对右子树进行遍历。

• 方法二：迭代法：

  1. 初始化一个空栈。
  2. 当根节点不为空或栈不为空时，执行以下操作：
     • 若根节点不为空，将其压入栈中，并将根节点更新为其左子节点。
     • 若根节点为空，从栈中弹出一个节点，将其值添加到结果列表中，并将根节点更新为其右子节点。

C语言代码实现

#include <stdio.h>
#include <stdlib.h>

// 定义二叉树节点结构体
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

// 创建新的二叉树节点
struct TreeNode* newNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 方法一：递归法
// 中序遍历的辅助函数，使用递归实现
// 参数 root 为当前处理的二叉树节点，res 为存储遍历结果的整数数组指针，returnSize 为结果数组的大小指针
// 此函数不直接返回结果数组，而是通过修改 res 和 returnSize 来传递结果
// 注意：使用全局变量或静态变量存储结果会导致函数不可重入，不推荐
void inorderTraversalHelper(struct TreeNode* root, int* res, int* returnSize) {
    if (root == NULL) {
        return;
    }
    inorderTraversalHelper(root->left, res, returnSize);  // 先遍历左子树
    res[(*returnSize)++] = root->val;  // 访问根节点并添加到结果数组中
    inorderTraversalHelper(root->right, res, returnSize);  // 再遍历右子树
}

// 中序遍历的主函数，使用递归
// 参数 root 为二叉树的根节点
// 返回一个存储中序遍历结果的整数数组指针
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    int* res = (int*)malloc(1000 * sizeof(int));  // 先分配一定大小的内存，实际使用中可按需调整或使用动态扩展内存的方法
    *returnSize = 0;
    inorderTraversalHelper(root, res, returnSize);
    return res;
}

// 方法二：迭代法
// 中序遍历的主函数，使用迭代实现
// 参数 root 为二叉树的根节点
// 返回一个存储中序遍历结果的整数数组指针
int* inorderTraversalIterative(struct TreeNode* root, int* returnSize) {
    int* res = (int*)malloc(1000 * sizeof(int));  // 先分配一定大小的内存，实际使用中可按需调整或使用动态扩展内存的方法
    *returnSize = 0;
    struct TreeNode** stack = (struct TreeNode**)malloc(1000 * sizeof(struct TreeNode*));  // 存储节点的栈
    int top = 0;  // 栈顶指针
    while (root || top > 0) {
        if (root) {
            stack[top++] = root;  // 将当前节点压入栈中
            root = root->left;  // 向左子树移动
        } else {
            root = stack[--top];  // 弹出栈顶节点
            res[(*returnSize)++] = root->val;  // 访问节点并添加到结果数组中
            root = root->right;  // 向右子树移动
        }
    }
    free(stack);  // 释放栈内存
    return res;
}


int main() {
    // 构建测试用的二叉树
    struct TreeNode* root = newNode(1);
    root->right = newNode(2);
    root->right->left = newNode(3);

    int returnSize1, returnSize2;
    int* res1 = inorderTraversal(root, &returnSize1);
    int* res2 = inorderTraversalIterative(root, &returnSize2);

    // 打印递归法的结果
    printf("Recursive Inorder Traversal: ");
    for (int i = 0; i < returnSize1; i++) {
        printf("%d ", res1[i]);
    }
    printf("\n");
    free(res1);  // 释放递归法的结果数组内存

    // 打印迭代法的结果
    printf("Iterative Inorder Traversal: ");
    for (int i = 0; i < returnSize2; i++) {
        printf("%d ", res2[i]);
    }
    printf("\n");
    free(res2);  // 释放迭代法的结果数组内存

    return 0;
}

代码解释：

• newNode 函数：

  • 功能：创建一个新的二叉树节点，为节点分配内存，并初始化节点的值和左右子节点指针。
  • 参数：
    • val：节点的值。
  • 代码逻辑：
    • 使用 malloc 分配内存。
    • 初始化节点的值和左右子节点指针为 NULL。

• inorderTraversalHelper 函数（递归辅助函数）：

  • 功能：递归地进行中序遍历，将结果存储在 res 数组中，并更新 returnSize。
  • 参数：
    • root：当前处理的二叉树节点。
    • res：存储遍历结果的整数数组指针。
    • returnSize：结果数组的大小指针，通过指针修改其值。
  • 代码逻辑：
    • 若 root 为 NULL，返回。
    • 先递归调用自身处理左子树。
    • 存储当前节点值到 res 数组并更新 returnSize。
    • 再递归调用自身处理右子树。

• inorderTraversal 函数（递归主函数）：

  • 功能：进行二叉树的中序遍历，调用 inorderTraversalHelper 函数并处理结果数组内存分配。
  • 参数：
    • root：二叉树的根节点。
    • returnSize：结果数组的大小指针。
  • 代码逻辑：
    • 分配存储结果的内存。
    • 调用 inorderTraversalHelper 函数进行遍历。

• inorderTraversalIterative 函数（迭代主函数）：

  • 功能：使用迭代的方式进行中序遍历。
  • 参数：
    • root：二叉树的根节点。
    • returnSize：结果数组的大小指针。
  • 代码逻辑：
    • 分配存储结果和栈的内存。
    • 当 root 不为空或栈不为空时：
      • 若 root 不为空，将其压入栈中并更新 root 为左子节点。
      • 若 root 为空，弹出栈顶节点，存储节点值，更新 root 为右子节点。
    • 释放栈的内存。

• main 函数：

  • 功能：构建测试用的二叉树，调用两种遍历方法，并打印结果，最后释放内存。
  • 代码逻辑：
    • 构建测试二叉树。
    • 调用递归和迭代的中序遍历函数并打印结果。
    • 释放结果数组的内存。

请注意，在实际使用中，对于内存分配和释放需要特别小心，确保不会出现内存泄漏。对于结果数组的内存分配，可根据实际情况使用更灵活的动态内存分配方法，例如使用 realloc 按需扩展内存。同时，两种遍历方法都需要注意处理边界情况，确保在不同结构的二叉树上都能正常工作。