C语言二叉树前序遍历DFS实现问题求助：数组相关疑问

你当前代码的核心问题：每次递归都往ans[0]写值，会覆盖之前的结果；returnSize硬编码为10，完全不符合实际节点数量；数组长度没有根据树的节点数动态分配。下面逐个解决你的疑问：

1. 如何获取二叉树节点数量来确定数组长度？ #

可以先写一个辅助函数，通过遍历二叉树统计总节点数。只要遍历每个节点一次就能数出总数，比如用递归实现：

int countNodes(struct TreeNode* root) {
    if (root == NULL) return 0;
    return 1 + countNodes(root->left) + countNodes(root->right);
}

调用这个函数就能得到节点总数，用这个数值来malloc数组，既不会浪费空间，也不会出现长度不足的问题。

2. 是否可以不创建数组来实现该功能？ #

不行。题目明确要求返回一个malloc分配的数组来存储遍历结果，且调用者会负责后续的free操作。就算你先用链表暂存遍历结果，最后还是要把链表转成数组才能满足返回要求，所以绕不开数组的创建。

3. 如何正确将节点值依次添加到数组中？ #

需要一个可变的索引来跟踪当前数组的写入位置，这个索引必须通过指针传递给递归函数（因为递归过程中需要修改索引的值）。修正后的完整代码如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

// 统计节点数的辅助函数
int countNodes(struct TreeNode* root) {
    if (root == NULL) return 0;
    return 1 + countNodes(root->left) + countNodes(root->right);
}

// 带索引指针的递归遍历函数
void dfs(struct TreeNode* root, int* ans, int* idx) {
    if (root == NULL) return;
    // 写入当前节点值，同时索引自增
    ans[(*idx)++] = root->val;
    dfs(root->left, ans, idx);
    dfs(root->right, ans, idx);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    // 先获取节点总数，赋值给returnSize
    *returnSize = countNodes(root);
    // 空树直接返回NULL，避免无效内存分配
    if (*returnSize == 0) return NULL;
    // 根据节点数分配数组空间
    int* ans = malloc(*returnSize * sizeof(int));
    int idx = 0;
    dfs(root, ans, &idx);
    return ans;
}

这段代码的逻辑：

• 先统计节点数，确定数组长度和返回的returnSize；
• 递归时通过索引指针idx跟踪写入位置，保证每个节点值依次存入数组的不同下标；
• 处理了空树的边界情况，避免不必要的内存操作。

你也可以用迭代方式（栈模拟递归）实现，思路是用栈存储待遍历的节点，同样需要先统计节点数或者动态扩容数组，但递归方式更直观，适合刚接触二叉树的学习场景。

内容的提问来源于stack exchange，提问作者user20977916