[数据结构与算法]103. 二叉树的锯齿形层序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
#define NODE_SIZE 10000
int** zigzagLevelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
    if(root==NULL) {
        *returnSize = 0;
        return NULL;
    }
    int** zzlOrder = (int**)malloc(sizeof(int*)*NODE_SIZE);
    int row = 0;
    int col = 0;
    *returnColumnSizes = (int*)malloc(sizeof(int)*NODE_SIZE);
    struct TreeNode* stk1[NODE_SIZE];
    struct TreeNode* stk2[NODE_SIZE];
    struct TreeNode* pNode = NULL;
    int top1 = -1;
    int top2 = -1;
    stk1[++top1] = root;
    
    while (top1!=-1 || top2!=-1) {
        
        zzlOrder[row] = (int* )malloc(sizeof(int)*NODE_SIZE);
        while(top1!=-1){
            pNode = stk1[top1--];
            zzlOrder[row][col++] = pNode->val;
            if(pNode->left!=NULL) stk2[++top2] = pNode->left;
            if(pNode->right!=NULL) stk2[++top2] = pNode->right;
        }
        (*returnColumnSizes)[row++] = col;
        col=0;
        if(top2==-1) break;

        zzlOrder[row] = (int* )malloc(sizeof(int)*NODE_SIZE);
        while(top2!=-1){
            pNode = stk2[top2--];
            zzlOrder[row][col++] = pNode->val;
            if(pNode->right!=NULL) stk1[++top1] = pNode->right;
            if(pNode->left!=NULL) stk1[++top1] = pNode->left;
        }
        (*returnColumnSizes)[row++] = col;
        col=0;
    }
    *returnSize = row;
    return zzlOrder;
}