Accepted C Solution using Morris Traversal, preorder


  • 0
    B

    In https://leetcode.com/discuss/44194/accepted-c-solution-using-morris-traversal I get to know the Morris Traversal, and I did the so called little modification, it works well and have a good runtime.

      /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     struct TreeNode *left;
     *     struct TreeNode *right;
     * };
     */
    /**
     * Return an array of size *returnSize.
     * Note: The returned array must be malloced, assume caller calls free().
     */
    int* inorderTraversal(struct TreeNode* root, int* returnSize) {
        *returnSize = 0;
        int values[255];
        //= malloc(255*sizeof(int));
        struct TreeNode *curr = root;
        struct TreeNode *tmp = NULL; // maybe useless?
        while(curr)
        {
            if(curr->left)
            {
                tmp = curr->left;
                while(tmp->right != curr && tmp->right != NULL )
                {
                    tmp = tmp->right;
                }
                if( tmp->right == curr )
                {
                    tmp->right = NULL;
                    values[(*returnSize)++] = curr->val;
                    curr = curr->right;
                }
                else
                {
                    tmp->right = curr;
                    curr = curr->left;
                }
                    
            }
            else
            {
                values[(*returnSize)++] = curr->val;
                curr = curr->right;
            }
            
        }
        
        int bs=sizeof(int)*(*returnSize);
        int *res=malloc(bs);
    
        memcpy(res,values,bs);
        return res;
    }

Log in to reply
 

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