Leetcode—103.二叉树的锯齿形层序遍历【中等】

2023每日刷题（二十六）

Leetcode—103.二叉树的锯齿形层序遍历

在这里插入图片描述

BFS实现代码

/**
 * 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 MAXSIZE 2003
int** zigzagLevelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {
    *returnSize = 0;
    if(root == NULL) {
        return NULL;
    }
    int** ans = (int **)malloc(sizeof(int*) * MAXSIZE);
    int front = 0, rear = 0;
    int len = 0;
    struct TreeNode** queue = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * MAXSIZE);
    *returnColumnSizes = (struct TreeNode*)malloc(sizeof(struct TreeNode) * MAXSIZE);
    
    queue[rear++] = root;
    while(front != rear) {
        len = rear - front;
        ans[*returnSize] = (int *)malloc(sizeof(int) * len);
        int level = *returnSize;
        int cnt = 0;
        if(level % 2 == 0) {
            while(len > 0) {
                len--;
                struct TreeNode* p = queue[front++];
                ans[*returnSize][cnt++] = p->val;
                if(p->left != NULL) {
                    queue[rear++] = p->left;
                }
                if(p->right != NULL) {
                    queue[rear++] = p->right;
                }
            }
        } else {
            int tmp = front;
            while(len > 0) {
                len--;
                struct TreeNode* p = queue[front++];
                struct TreeNode* q = queue[tmp + len];
                ans[*returnSize][cnt++] = q->val;
                if(p->left != NULL) {
                    queue[rear++] = p->left;
                }
                if(p->right != NULL) {
                    queue[rear++] = p->right;
                }
            }
        }
        (*returnColumnSizes)[*returnSize] = cnt;
        (*returnSize)++;
    }
    return ans;
}