C solution (0ms) - Morris Traversal i.e no stack, no recursion


  • 0
    int* inorderTraversal(struct TreeNode* root, int* numNodes) {
        if (!root) { *numNodes = 0; return NULL; }
        struct TreeNode *pred, *curr = root;
        int *result = NULL;
        while (curr) {
            if (curr->left == NULL) {
                (*numNodes)++;
                result = realloc(result, *numNodes * sizeof(int));
                result[(*numNodes) - 1] = curr->val;
                curr = curr->right;
                continue;
            }
            pred = curr->left;
            while (pred->right && pred->right != curr) {
                pred = pred->right;
            }
            if (!pred->right) {
                pred->right = curr;
                curr = curr->left;
            } else {
                pred->right = NULL;
                (*numNodes)++;
                result = realloc(result, *numNodes * sizeof(int));
                result[(*numNodes) - 1] = curr->val;
                curr = curr->right;
            }
        }
        return result;
    }
    

Log in to reply
 

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