Problem with deepth first search and create array-CodePudding

I recently started programming on c and I have a problem with the code. I need, given the root of a binary tree, to return the previous traversal of its node values. This is my code now.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
void dfs(struct TreeNode *root, int *ans);

int *preorderTraversal(struct TreeNode *root, int *returnSize) {
    int *ans = malloc(10 * sizeof(int));
    dfs(root, ans);
    *returnSize = 10;
    return ans;
}

void dfs(struct TreeNode *root, int *ans) {
    if (root == NULL)
        return ;
    ans[0] = root->val;
    dfs(root->left, ans);
    dfs(root->right, ans);
}

I know it looks terrible and that it won't work at all, so I have a few questions:

To create an array, I need to specify his length, but I really don't understand how I can get it.
Also is it possible to execute this code without creating an array?
And how exactly should I add root->val and all other elements after it to the array.

CodePudding user response：

Given:

#define UNUSED( x ) (void)( x )

typedef struct Node {
   int val;
   struct Node *left;
   struct Node *right;
} Node;

typedef void (*Visitor)( Node *, void * );

void dfs( Node *node, Visitor visitor, void *param ) {
   if ( !node )
      return;

   dfs( node->left,  visitor, param );
   dfs( node->right, visitor, param );

   visitor( node, param );
}

Solution 1: Two traversals

typedef struct {
   size_t i;
   int *a;
} AppendVisitorData;

void counter_visitor( Node *node, void *param ) {
   UNUSED( node );
   size_t *count_ptr = param;

     *count_ptr;
}

void append_visitor( Node *node, void *param ) {
   AppendVisitorData *data = param;

   data->a[ data->i   ] = node->val;
}

int doit( Node *node, size_t *n_ptr, int **a_ptr ) {
   dfs( node, counter_visitor, n_ptr );

   *a_ptr = malloc( *n_ptr * sizeof( int ) );

   AppendVisitorData data = {
      .i = 0,
      .a = *a_ptr,
   };

   dfs( node, append_visitor, &data );

   return 0;
}

Solution 2: Grow array

typedef struct {
   size_t n;
   size_t i;
   int *a;
} AppendVisitorData;

void append_visitor( Node *node, void *param ) {
   AppendVisitorData *data = param;

   if ( data->i == data->n ) {
      if ( data->n ) 
         data->n *= 2;
      else
         data->n = 8;

      data->a = realloc( data->a, data->n * sizeof( int ) );
   }

   data->a[ data->i   ] = node->val;
}

int doit( Node *node, size_t *n_ptr, int **a_ptr ) {
   AppendVisitorData data = {
      .n = 0,
      .i = 0,
      .a = NULL,
   };

   dfs( node, append_visitor, &data );

   *a_ptr = realloc( data.a, data.i * sizeof( int ) );
   *n_ptr = data.i;
   return 0;
}

Error checking left to user.