题解 | #按之字形顺序打印二叉树#

C语言

//做这道题的时候，一直想着怎么按照是否反转来压栈，陷入了死胡同，看答案后，发现可以按照是否反转来弹栈，多思考不同的方法

int** Print(struct TreeNode* pRoot, int* returnSize, int** returnColumnSizes ) {

    // write code hereI

    if(!pRoot) return NULL;

    *returnSize = -1;  

    *returnColumnSizes =  (int*)malloc(sizeof(int)*1000);

    int **res = (int**)malloc(sizeof(int*) * 1000);

    struct TreeNode** st1 = (struct TreeNode**)malloc(sizeof(struct TreeNode*)*3000);

    struct TreeNode** st2 = (struct TreeNode**)malloc(sizeof(struct TreeNode*)*3000);

    // struct TreeNode *st1[6], *st2[6];       //调试代码

    // int res[4][8] = {0};                    //调试代码

    int st1_i = -1, st2_i = -1;

    int st2_i_Max;      //用来装当前st2存储的元素最大数量

    int LayerNodeCnt, tmpCnt;

    int reverseFlag = 1;

    struct TreeNode* node;

    st1[++st1_i] = pRoot;

    while(st1_i >= 0){

        if(st1[st1_i] != NULL){

            //先将st1的元素弹栈到st2

            while(st1_i >= 0){

                st2[++st2_i] = st1[st1_i--];

            }

            st2_i_Max = st2_i;

            //根据reverseFlag来将st2的子节点压入st1

            while(st2_i >= 0){

                node = st2[st2_i];

                if(node->left)st1[++st1_i] = node->left;

                if(node->right)st1[++st1_i] = node->right;  

                st2_i--;

            }

            //将当前层节点加上标志压入st1

            st2_i = st2_i_Max;

            LayerNodeCnt = st2_i_Max+1;

            while(st2_i >= 0){

                st1[++st1_i] = st2[st2_i--];

                st1[++st1_i] = NULL;

            }

            (*returnColumnSizes)[++(*returnSize)] = LayerNodeCnt;

            res[(*returnSize)] = (int*)malloc(sizeof(int)*LayerNodeCnt);

            st2_i_Max = 0, tmpCnt=0;

            reverseFlag = !reverseFlag; //为下一次反转

        }else{

            st1_i--;

            if(reverseFlag){        //根据是否反转来选择弹栈元素的存储位置（从前还是从后）

                res[*returnSize][tmpCnt] = st1[st1_i--]->val;

            }else{

                res[*returnSize][LayerNodeCnt-tmpCnt-1] = st1[st1_i--]->val;

            }

            tmpCnt++;

        }

    }

    (*returnSize)++;

    return (int **)res;

}