本次刷题顺序是按照卡尔的代码随想录中给出的顺序
今天的刷题内容是二叉树的层次遍历，基本上都是一个套路
- 第一层循环是队列不为空时，继续循环
- 第二层循环是当前层未遍历完时，继续循环(在遍历当前层的结点时，将该结点的非空左右子结点入队列)
一个思想框架，直接怒斩leetcode十道题，啊哈哈哈，下面开干！
补充说明：
今天写代码的时候，存储树结点的“容器”，我写成了“st”，但是实际上是用的队列，由于题目还挺多的，懒得一个个改了，可以把st当成qu
102. 二叉树的层序遍历
/*** 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().*/
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {int** res = malloc(sizeof(int*) * 2000);*returnColumnSizes = malloc(sizeof(int*) * 2000);*returnSize = 0;struct TreeNode** st = malloc(sizeof(struct TreeNode*) * 2000);struct TreeNode* tmp;int rear = -1, mid_rear, front = -1, idx;if(root == NULL) return res;st[++rear] = root;mid_rear = rear;/*队列为空，则结束循环*/while(rear != front) {idx = 0;(*returnColumnSizes)[*returnSize] = mid_rear - front;res[*returnSize] = malloc(sizeof(int) * (mid_rear - front));while(front < mid_rear) {//当前层未遍历完时，则继续遍历tmp = st[++front];res[*returnSize][idx++] = tmp->val;if(tmp->left) st[++rear] = tmp->left;if(tmp->right) st[++rear] = tmp->right;}(*returnSize)++;mid_rear = rear;//因为在内层循环中，rear会边，所以用mid_rear记录上一层遍历结束时的队尾}return res;
}107. 二叉树的层序遍历 II
/*** 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().*/
int** levelOrderBottom(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {int** res = malloc(sizeof(int*) * 2001);*returnColumnSizes = malloc(sizeof(int) * 2001);*returnSize = 0;if(root == NULL) return res;struct TreeNode** st = malloc(sizeof(struct TreeNode*) * 2001);struct TreeNode* tmp;int rear = -1, mid_rear, front = -1, idx;st[++rear] = root;mid_rear = rear;while(rear != front) {(*returnColumnSizes)[*returnSize] = mid_rear - front;res[*returnSize] = malloc(sizeof(int) * (mid_rear - front));idx = 0;while(front != mid_rear) {tmp = st[++front];res[*returnSize][idx++] = tmp->val;if(tmp->left) st[++rear] = tmp->left;if(tmp->right) st[++rear] = tmp->right;}(*returnSize)++;mid_rear = rear;}//对结果进行翻转int* mid_p, mid;for(idx = 0; 2 * idx < (*returnSize); idx++) {mid_p = res[idx];res[idx] = res[(*returnSize) - 1 - idx];res[(*returnSize) - 1 - idx] = mid_p;mid = (*returnColumnSizes)[idx];(*returnColumnSizes)[idx] = (*returnColumnSizes)[(*returnSize) - 1 - idx];(*returnColumnSizes)[(*returnSize) - 1 - idx] = mid;} return res;
}199. 二叉树的右视图
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
/*** Note: The returned array must be malloced, assume caller calls free().*/
int* rightSideView(struct TreeNode* root, int* returnSize) {int* res = malloc(sizeof(int) * 100);*returnSize = 0;if(root == NULL) return res;struct TreeNode** st = malloc(sizeof(struct TreeNode*) * 100);struct TreeNode* tmp;int rear = -1, mid_rear, front = -1;st[++rear] = root;mid_rear = rear;while(rear != front) {res[(*returnSize)] = st[mid_rear]->val;while(mid_rear != front) {tmp = st[++front];if(tmp->left) st[++rear] = tmp->left;if(tmp->right) st[++rear] = tmp->right;}(*returnSize)++;mid_rear = rear;}return res;
}637. 二叉树的层平均值
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
/*** Note: The returned array must be malloced, assume caller calls free().*/
double* averageOfLevels(struct TreeNode* root, int* returnSize) {double* res = malloc(sizeof(int) * 10000);*returnSize = 0;if(root == NULL) return res;struct TreeNode** st = malloc(sizeof(struct TreeNode*) * 10000);struct TreeNode* tmp;int rear = -1, mid_rear, front = -1, len;long long sum;st[++rear] = root;mid_rear = rear;while(rear != front) {sum = 0;len = mid_rear - front;while(mid_rear != front) {tmp = st[++front];sum += tmp->val;if(tmp->left) st[++rear] = tmp->left;if(tmp->right) st[++rear] = tmp->right;}res[(*returnSize)] = (double)sum/len;(*returnSize)++;mid_rear = rear;}return res;
}429. N 叉树的层序遍历
/*** Definition for a Node.* struct Node {* int val;* int numChildren;* struct Node** children;* };*//*** 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().*/
int** levelOrder(struct Node* root, int* returnSize, int** returnColumnSizes) {int** res = malloc(sizeof(int*) * 10001);*returnColumnSizes = malloc(sizeof(int*) * 10001);*returnSize = 0;struct Node** st = malloc(sizeof(struct Node*) * 10001);struct Node* tmp;int rear = -1, mid_rear, front = -1, idx, ch_idx;if(root == NULL) return res;st[++rear] = root;mid_rear = rear;/*队列为空，则结束循环*/while(rear != front) {idx = 0;(*returnColumnSizes)[*returnSize] = mid_rear - front;res[*returnSize] = malloc(sizeof(int) * (mid_rear - front));while(front < mid_rear) {//当前层未遍历完时，则继续遍历ch_idx = 0;tmp = st[++front];res[*returnSize][idx++] = tmp->val;while(ch_idx < tmp->numChildren) {if(tmp->children[ch_idx]) st[++rear] = tmp->children[ch_idx++];}}(*returnSize)++;mid_rear = rear;//因为在内层循环中，rear会边，所以用mid_rear记录上一层遍历结束时的队尾}return res;
}515. 在每个树行中找最大值
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
/*** Note: The returned array must be malloced, assume caller calls free().*/
int* largestValues(struct TreeNode* root, int* returnSize) {int* res = malloc(sizeof(int) * 10001);*returnSize = 0;if(root == NULL) return res;struct TreeNode** st = malloc(sizeof(struct TreeNode*) * 10001);struct TreeNode* tmp;int rear = -1, mid_rear, front = -1, mid_max;st[++rear] = root;mid_rear = rear;while(rear != front) {mid_max = INT_MIN;while(mid_rear != front) {tmp = st[++front];mid_max = mid_max >= tmp->val ? mid_max : tmp->val;if(tmp->left) st[++rear] = tmp->left;if(tmp->right) st[++rear] = tmp->right;}res[(*returnSize)] = mid_max;(*returnSize)++;mid_rear = rear;}return res;
}116. 填充每个节点的下一个右侧节点指针
/*** Definition for a Node.* struct Node {* int val;* struct Node *left;* struct Node *right;* struct Node *next;* };*/struct Node* connect(struct Node* root) {if(root == NULL) return NULL;struct Node** st = malloc(sizeof(struct Node*) * pow(2, 12));struct Node* tmp;int rear = -1, mid_rear, front = -1, mid_max;st[++rear] = root;mid_rear = rear;while(rear != front) {while(mid_rear != front) {tmp = st[++front];if(front < mid_rear) tmp->next = st[front + 1];else tmp->next = NULL;//判断子树是否需要入队列if(tmp->left) st[++rear] = tmp->left;if(tmp->right) st[++rear] = tmp->right;}mid_rear = rear;}return st[0];
}117. 填充每个节点的下一个右侧节点指针 II
/*** Definition for a Node.* struct Node {* int val;* struct Node *left;* struct Node *right;* struct Node *next;* };*/struct Node* connect(struct Node* root) {if(root == NULL) return NULL;struct Node** st = malloc(sizeof(struct Node*) * 6001);struct Node* tmp;int rear = -1, mid_rear, front = -1, mid_max;st[++rear] = root;mid_rear = rear;while(rear != front) {while(mid_rear != front) {tmp = st[++front];if(front < mid_rear) tmp->next = st[front + 1];else tmp->next = NULL;//判断子树是否需要入队列if(tmp->left) st[++rear] = tmp->left;if(tmp->right) st[++rear] = tmp->right;}mid_rear = rear;}return st[0];
}104. 二叉树的最大深度
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
int maxDepth(struct TreeNode* root) {if(root == NULL) return 0;struct TreeNode** st = malloc(sizeof(struct TreeNode*) * 10001);struct TreeNode* tmp;int rear = -1, mid_rear, front = -1, sum = 0;st[++rear] = root;mid_rear = rear;while(rear != front) {while(mid_rear != front) {tmp = st[++front];//判断子树是否需要入队列if(tmp->left) st[++rear] = tmp->left;if(tmp->right) st[++rear] = tmp->right;}sum++;mid_rear = rear;}return sum;
}111. 二叉树的最小深度
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
int minDepth(struct TreeNode* root) {if(root == NULL) return 0;struct TreeNode** st = malloc(sizeof(struct TreeNode*) * 100001);struct TreeNode* tmp;int rear = -1, mid_rear, front = -1, sum = 0;st[++rear] = root;mid_rear = rear;while(rear != front) {sum++;while(mid_rear != front) {tmp = st[++front];//判断子树是否需要入队列if(tmp->left) st[++rear] = tmp->left;if(tmp->right) st[++rear] = tmp->right;if(!tmp->left && !tmp->right) return sum;}mid_rear = rear;}return sum;
}