Share my solution in C


  • 6
    M

    ///// iterative solution

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

    }

    //// recursive solution

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

    }


Log in to reply
 

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