/**

 * 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().

 */

int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes)

{

    struct TreeNode *queue[2001];

    int front = 0, rear = 0;

    if (root != NULL) {

        queue[rear++] = root;

    }

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

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

    *returnSize = 0;

    while (front < rear) {

        int colIndex = 0;

        // 申请内存

        int last = rear;

        res[(*returnSize)] = (int *)malloc(sizeof(int) * (last - front));

        while (front < last) {

            // 取出当前节点

            struct TreeNode *curNode = queue[front++];

            res[(*returnSize)][colIndex++] = curNode->val;

            if (curNode->left != NULL) {

                queue[rear++] = curNode->left;

            }

            if (curNode->right != NULL) {

                queue[rear++] = curNode->right;

            }

        }

        (*returnColumnSizes)[(*returnSize)] = colIndex;

        (*returnSize)++;

    }

    return res;

}

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     struct TreeNode *left;

 *     struct TreeNode *right;

 * };

 */

void Swap(struct TreeNode **left, struct TreeNode **right)

{

    // printf("begin left:%p, right:%p\n", left, right);

    struct TreeNode *tmp = *left;

    *left = *right;

    *right = tmp;

    // printf("end left:%p, right:%p\n", left, right);

}

struct TreeNode* invertTree(struct TreeNode* root)

{

    if (root == NULL) {

        return root;

    }

    // 前序：中 左 右

    // printf("Swap前 end left:%p, right:%p\n", root->left, root->right);

    Swap(&root->left, &root->right);

    // printf("Swap后 end left:%p, right:%p\n", root->left, root->right);

    // struct TreeNode* temp = root->left;

    // root->left = root->right;

    // root->right = temp;

    invertTree(root->left);

    invertTree(root->right);

    return root;

}

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     struct TreeNode *left;

 *     struct TreeNode *right;

 * };

 */

void Swap(struct TreeNode **left, struct TreeNode **right)

{

    struct TreeNode *tmp = *left;

    *left = *right;

    *right = tmp;

}

struct TreeNode* invertTree(struct TreeNode* root)

{

    struct TreeNode *stack[10];

    int index = 0;

    if (root != NULL) {

        stack[index++] = root;

    }

    while (index != 0) {

        // 取出当前节点（准备交换左右子节点）

        struct TreeNode *curNode = stack[--index];

        if (curNode == NULL) {

            break;

        }

        Swap(&curNode->left, &curNode->right);

        // 上面已经交换完了，这里安装前序遍历正常顺序（如果不是翻转的需要则逆序，由于是栈）

        if (curNode->left != NULL) {

            stack[index++] = curNode->left;

        }

        if (curNode->right != NULL) {

            stack[index++] = curNode->right;

        }

    }

    return root;

}