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

本文主要是介绍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;
}