1.题目要求:
给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
2.做题思路:由题我们可以判断，树中每到偶数层时，就会逆置，所以我们可以采用层序遍历和逆置函数的方法来解此题
3.做题步骤:
1.我们先把层序遍历所需要的队列结构，出队和入队函数写好：
//创建队列
typedef struct queue{struct TreeNode* value;struct queue* next;
}queue_t;
//入队
void push(queue_t** head,struct TreeNode* data){queue_t* newnode = (queue_t*)malloc(sizeof(queue_t));newnode->value = data;newnode->next = NULL;if(*head == NULL){*head = newnode;return;}queue_t* tail = *head;while(tail->next != NULL){tail = tail->next;}tail->next = newnode;
}
//出队
struct TreeNode* pop(queue_t** head){struct TreeNode* x = (*head)->value;(*head) = (*head)->next;return x;
}
2.写好逆置函数:
void reverse(int* number,int left,int right){while(left <= right){int temp = number[left];number[left] = number[right];number[right] = temp;left++;right--;}
}
3.写好进行层序遍历的变量:
*returnSize = 0;if(root == NULL){return NULL;}int* each_line_nodes = (int*)malloc(sizeof(int)*2000);//记录每行结点数int j_1 = 0;int* level_order_number = (int*)malloc(sizeof(int)* 2000);//层序遍历的数组int j_2 = 0;int depth = 0;//树的高度int count = 1;//根结点的个数int index = 0;//记录每层的第一个的索引int nextcount = 0;//下一个结点的个数int size = 0;//记录队列中的个数queue_t* quence = NULL;//设置队列
4.进行层序遍历:
//进行层序遍历push(&quence,root);size++;while(size != 0){depth++;for(int i = 0;i < count;i++){struct TreeNode* temp = pop(&quence);size--;level_order_number[j_2] = temp->val;j_2++;if(temp->left != NULL){push(&quence,temp->left);size++;nextcount++;}if(temp->right != NULL){push(&quence,temp->right);size++;nextcount++;}}each_line_nodes[j_1] = count;j_1++;//如果高度为偶数时，就要对数组这一次的元素进行逆置if(depth % 2 == 0){reverse(level_order_number,index,j_2 - 1);index += count;}else{index += count;}count = nextcount;nextcount = 0;}
5.再创造二维数组，把值放入二维数组中:
//设立二维数组int** array = (int**)malloc(sizeof(int*)* depth);for(int i = 0;i < depth;i++){array[i] = (int*)malloc(sizeof(int) * each_line_nodes[i]);}int f = 0;for(int i = 0;i < depth;i++){for(int j = 0;j < each_line_nodes[i];j++){array[i][j] = level_order_number[f];f++;}}*returnSize = depth;*returnColumnSizes = (int*)malloc(sizeof(int) * (*returnSize));for(int i = 0;i < depth;i++){(*returnColumnSizes)[i] = each_line_nodes[i];}return array;
以下为全部代码:
/*** 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().*///创建队列
typedef struct queue{struct TreeNode* value;struct queue* next;
}queue_t;
//入队
void push(queue_t** head,struct TreeNode* data){queue_t* newnode = (queue_t*)malloc(sizeof(queue_t));newnode->value = data;newnode->next = NULL;if(*head == NULL){*head = newnode;return;}queue_t* tail = *head;while(tail->next != NULL){tail = tail->next;}tail->next = newnode;
}
//出队
struct TreeNode* pop(queue_t** head){struct TreeNode* x = (*head)->value;(*head) = (*head)->next;return x;
}
void reverse(int* number,int left,int right){while(left <= right){int temp = number[left];number[left] = number[right];number[right] = temp;left++;right--;}
}
int** zigzagLevelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {*returnSize = 0;if(root == NULL){return NULL;}int* each_line_nodes = (int*)malloc(sizeof(int)*2000);//记录每行结点数int j_1 = 0;int* level_order_number = (int*)malloc(sizeof(int)* 2000);//层序遍历的数组int j_2 = 0;int depth = 0;//树的高度int count = 1;//根结点的个数int index = 0;//记录每层的第一个的索引int nextcount = 0;//下一个结点的个数int size = 0;//记录队列中的个数queue_t* quence = NULL;//设置队列//进行层序遍历push(&quence,root);size++;while(size != 0){depth++;for(int i = 0;i < count;i++){struct TreeNode* temp = pop(&quence);size--;level_order_number[j_2] = temp->val;j_2++;if(temp->left != NULL){push(&quence,temp->left);size++;nextcount++;}if(temp->right != NULL){push(&quence,temp->right);size++;nextcount++;}}each_line_nodes[j_1] = count;j_1++;//如果高度为偶数时，就要对数组这一次的元素进行逆置if(depth % 2 == 0){reverse(level_order_number,index,j_2 - 1);index += count;}else{index += count;}count = nextcount;nextcount = 0;} //设立二维数组int** array = (int**)malloc(sizeof(int*)* depth);for(int i = 0;i < depth;i++){array[i] = (int*)malloc(sizeof(int) * each_line_nodes[i]);}int f = 0;for(int i = 0;i < depth;i++){for(int j = 0;j < each_line_nodes[i];j++){array[i][j] = level_order_number[f];f++;}}*returnSize = depth;*returnColumnSizes = (int*)malloc(sizeof(int) * (*returnSize));for(int i = 0;i < depth;i++){(*returnColumnSizes)[i] = each_line_nodes[i];}return array;
}
好了，这就是我的解题方法，大家如果觉得好的话，不妨给个免费的赞吧，谢谢了^ _ ^