My C code using BFS, easy to understand.


  • -1
    W
    void zigzag(int* nums, int len, struct TreeNode** last, int flag)
    {
    int i = 0;
    struct TreeNode** front;
    if (flag == 0) {
        front = last - len + 1;
        for (; i < len; i++, front++) nums[i] = (*front)->val;
    }
    else
        for(; i < len; i++, last--) nums[i] = (*last)->val;
        
    return;
    }
    
    int** zigzagLevelOrder(struct TreeNode* root, int** columnSizes, int* returnSize) {
    
    if (root == NULL) return NULL;
    
    int** ret = (int**)malloc(sizeof(int*) * 1000);
    int* column = (int*)malloc(sizeof(int) * 1000);
    struct TreeNode* queue[3000] = {0}; 
    int curlen = 1, nextlen = 0, lvl = 0, head = 0, rear = 0;         
    column[lvl] = len;
    
    queue[rear++] = root;
    
    while (head != rear) {
        // dequeue
        root = queue[head++];
        
        // inqueue
        if (root->left != NULL) {
            queue[rear++] = root->left;
            nextlen++;
        }
        if (root->right != NULL) {
            queue[rear++] = root->right;  
            nextlen++;
        }
    
        curlen--;
        if (curlen == 0) {                                             // insert the cur level into the ret[lvl]
            ret[lvl] = (int*)malloc(sizeof(int) * column[lvl]);
            zigzag(ret[lvl], column[lvl], &queue[head-1], lvl%2);
            
            lvl++;
            curlen = column[lvl] = nextlen;
            nextlen = 0;
        }
    }
    
    *returnSize = lvl;
    *columnSizes = column;
    
    return ret;
    }

  • 0
    Y

    column[lvl] = len; // len is undefined ?


  • 0
    W

    sorry... that should be column[lvl] = curlen.


Log in to reply
 

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