力扣 103 题：二叉树的锯齿形层序遍历

力扣 103 题：二叉树的锯齿形层序遍历 C 语言实现详解

题目描述

给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左交替进行）。

例如：

给定二叉树 [3,9,20,null,null,15,7],3/ \9  20/  \15   7返回锯齿形层序遍历为：
[[3],[20,9],[15,7]
]

解决思路

层序遍历：本题可以看作普通层序遍历的变种，但需要在每一层节点遍历时决定输出方向。
锯齿形控制：
- 当层号为偶数时，从左到右存储节点。
- 当层号为奇数时，从右到左存储节点。
数据结构：
- 使用队列保存树节点进行层序遍历。
- 使用一个动态数组存储结果。

C 语言实现

核心代码

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>// 定义树节点结构体
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;
};// 定义队列节点结构体
struct QueueNode {struct TreeNode *node;struct QueueNode *next;
};// 定义队列操作
void enqueue(struct QueueNode **front, struct QueueNode **rear, struct TreeNode *node) {struct QueueNode *newNode = (struct QueueNode *)malloc(sizeof(struct QueueNode));newNode->node = node;newNode->next = NULL;if (*rear == NULL) {*front = *rear = newNode;} else {(*rear)->next = newNode;*rear = newNode;}
}struct TreeNode* dequeue(struct QueueNode **front, struct QueueNode **rear) {if (*front == NULL) return NULL;struct QueueNode *temp = *front;struct TreeNode *node = temp->node;*front = (*front)->next;if (*front == NULL) *rear = NULL;free(temp);return node;
}// 锯齿形层序遍历
int** zigzagLevelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {*returnSize = 0;if (root == NULL) return NULL;int **result = (int **)malloc(sizeof(int *) * 1000); // 预分配最大1000层*returnColumnSizes = (int *)malloc(sizeof(int) * 1000);struct QueueNode *front = NULL, *rear = NULL;enqueue(&front, &rear, root);bool leftToRight = true; // 控制遍历方向while (front != NULL) {int levelSize = 0;struct QueueNode *temp = front;// 统计当前层的节点数while (temp != NULL) {levelSize++;temp = temp->next;}result[*returnSize] = (int *)malloc(sizeof(int) * levelSize);(*returnColumnSizes)[*returnSize] = levelSize;int *tempResult = (int *)malloc(sizeof(int) * levelSize);int index = 0;// 遍历当前层for (int i = 0; i < levelSize; i++) {struct TreeNode *current = dequeue(&front, &rear);tempResult[index++] = current->val;if (current->left != NULL) {enqueue(&front, &rear, current->left);}if (current->right != NULL) {enqueue(&front, &rear, current->right);}}// 根据方向保存到结果if (leftToRight) {for (int i = 0; i < levelSize; i++) {result[*returnSize][i] = tempResult[i];}} else {for (int i = 0; i < levelSize; i++) {result[*returnSize][i] = tempResult[levelSize - i - 1];}}free(tempResult); // 释放临时结果leftToRight = !leftToRight; // 方向交替(*returnSize)++;}return result;
}

主函数测试代码

int main() {struct TreeNode node7 = {7, NULL, NULL};struct TreeNode node15 = {15, NULL, NULL};struct TreeNode node20 = {20, &node15, &node7};struct TreeNode node9 = {9, NULL, NULL};struct TreeNode root = {3, &node9, &node20};int returnSize = 0;int *returnColumnSizes = NULL;int **result = zigzagLevelOrder(&root, &returnSize, &returnColumnSizes);printf("锯齿形层序遍历结果:\n");for (int i = 0; i < returnSize; i++) {for (int j = 0; j < returnColumnSizes[i]; j++) {printf("%d ", result[i][j]);}printf("\n");free(result[i]); // 释放每一层的内存}free(result); // 释放结果数组free(returnColumnSizes); // 释放列大小数组return 0;
}