A recursive and an iterative solution both accepted with 0ms in C enclosed with a MorrisTraversal solution!


  • 0
    void traverse(struct TreeNode* root, int** arr, int* returnSize)
    {
        *returnSize += 1;
        *arr = (int*)realloc(*arr, sizeof(int)*(*returnSize));
        (*arr)[*returnSize-1] = root->val;
        if(root->left)
            traverse(root->left, arr, returnSize);
        if(root->right)
            traverse(root->right, arr, returnSize);
    }
    //AC - 0ms;
    int* preorderTraversal0(struct TreeNode* root, int* returnSize)
    {
        if(!root) return NULL;
        int* arr = (int*)malloc(sizeof(int));
        *returnSize = 0;
        traverse(root, &arr, returnSize);
        return arr;
    }
    
    void storeAndCollectLeftNodes(struct TreeNode* root, struct TreeNode*** stack, int* size, int** arr, int* returnSize)
    {
        while(root)
        {
            *returnSize += 1;
            *arr = (int*)realloc(*arr, sizeof(int)*(*returnSize));
            (*arr)[*returnSize-1] = root->val;
            *stack = (struct TreeNode**)realloc(*stack, sizeof(struct TreeNode*)*(*size+1));
            *size += 1;
            (*stack)[*size-1] = root;
            root = root->left;
        }
    }
    
    //AC - 0ms;
    int* preorderTraversal(struct TreeNode* root, int* returnSize)
    {
        if(!root) return NULL;
        int* arr = (int*)malloc(sizeof(int));
        *returnSize = 0;
        struct TreeNode** stack = (struct TreeNode**)malloc(sizeof(struct TreeNode*));
        int size = 0;
        storeAndCollectLeftNodes(root, &stack, &size, &arr, returnSize);
        while(size)
        {
            root = stack[size-1];
            size--;
            if(root->right) //handle the right children of leftmost nodes;
                storeAndCollectLeftNodes(root->right, &stack, &size, &arr, returnSize);
        }
        return arr;
    }
    
    //AC - 0ms - MorrisTraversal;
    int* preorderTraversal(struct TreeNode* root, int* returnSize)
    {
        if(!root) return NULL;
        int* arr = (int*)malloc(sizeof(int));
        *returnSize = 0;
        while(root)
        {
            if(!root->left)
            {
                *returnSize += 1;
                arr = (int*)realloc(arr, sizeof(int)*(*returnSize));
                arr[*returnSize-1] = root->val;
                root = root->right;
            }
            else
            {
                struct TreeNode* pre = root->left;
                while(pre->right && pre->right!=root)
                    pre = pre->right;
                if(!pre->right)
                {
                    *returnSize += 1;
                    arr = (int*)realloc(arr, sizeof(int)*(*returnSize));
                    arr[*returnSize-1] = root->val;
                    pre->right = root;
                    root = root->left;
                }
                else
                {
                    pre->right = NULL;
                    root = root->right;
                }
            }
        }
        return arr;
    }

Log in to reply
 

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