leetcode做题笔记103. 二叉树的锯齿形层序遍历

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

思路一：BFS

#define N 2000int** zigzagLevelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {*returnSize = 0;if (root == NULL) {return NULL;}int** ans = malloc(sizeof(int*) * N);*returnColumnSizes = malloc(sizeof(int) * N);struct TreeNode* nodeQueue[N];int left = 0, right = 0;nodeQueue[right++] = root;bool isOrderLeft = true;while (left < right) {int levelList[N * 2];int front = N, rear = N;int size = right - left;for (int i = 0; i < size; ++i) {struct TreeNode* node = nodeQueue[left++];if (isOrderLeft) {levelList[rear++] = node->val;} else {levelList[--front] = node->val;}if (node->left) {nodeQueue[right++] = node->left;}if (node->right) {nodeQueue[right++] = node->right;}}int* tmp = malloc(sizeof(int) * (rear - front));for (int i = 0; i < rear - front; i++) {tmp[i] = levelList[i + front];}ans[*returnSize] = tmp;(*returnColumnSizes)[*returnSize] = rear - front;(*returnSize)++;isOrderLeft = !isOrderLeft;}return ans;
}

分析：

本题与上题相似，直接使用广度优先搜索将每层数放入数组再输出即可，注意        (*returnColumnSizes)[*returnSize] = rear - front;

总结：

本题考察广度优先搜索算法，将每层按左向右再右向左的顺序放入数组再输出即可