Share my solution in C


  • 6
    M

    //// iterative solution

    int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    int *result = NULL;
    if (root == NULL)
        return result;
        
    *returnSize = 0;
    
    struct TreeNode **stack = (struct TreeNode **)malloc(sizeof(struct TreeNode *));
    struct TreeNode *pop;
    int length = 0;
    stack[length++] = root;
    
    while (length > 0) {
        result = (int *)realloc(result, (*returnSize+1)*sizeof(int));
        pop = stack[--length];
        result[*returnSize] = pop->val;
        *returnSize += 1;
        if (pop->right) {
            stack = (struct TreeNode **)realloc(stack, sizeof(struct TreeNode*)*(length+1));
            stack[length++] = pop->right;
        }
        if (pop->left) {
            stack = (struct TreeNode **)realloc(stack, sizeof(struct TreeNode*)*(length+1));
            stack[length++] = pop->left;
        }
    }
    free(stack);
    return result;
    

    }

    //// recursive solution

    int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    int *result = NULL;
    if (root == NULL)
        return result;
    result = (int *)malloc(sizeof(int));
    *result = root->val;
    
    int leftsize=0, rightsize=0, *leftarr, *rightarr;
    if (root->left)
        leftarr = preorderTraversal(root->left, &leftsize);
    if (root->right)
        rightarr = preorderTraversal(root->right, &rightsize);
    
    *returnSize = 1 + leftsize + rightsize;
    if (leftsize >0 || rightsize > 0)
        result = (int *)realloc(result, sizeof(int)*(*returnSize));
    
    int i, j;
    for (i=0; i<leftsize; i++)
        result[i+1] = leftarr[i];
    if (leftsize > 0)
        free(leftarr);
    for (j=0; j<rightsize; j++)
        result[i+j+1] = rightarr[j];
    if (rightsize > 0)
        free(rightarr);
        
    return result;
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.