队列 + bfs --- N 叉树的层序遍历 | 锯齿形层序遍历 | 二叉树最大宽度 | 每个树行中找最大值

一.429. N 叉树的层序遍历题目描述给定一个 N 叉树返回其节点值的层序遍历。即从左到右逐层遍历。树的序列化输入是用层序遍历每组子节点都由 null 值分隔参见示例。示例 1输入root [1,null,3,2,4,null,5,6]输出[[1],[3,2,4],[5,6]]示例 2输入root [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]输出[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]提示树的高度不会超过1000树的节点总数在[0, 104]之间解题思路队列bfs层序遍历先进先出使用的是队列利用队列来存储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(). */ //队列节点 typedef struct QueueNode{ struct Node* treeNode; struct QueueNode* next; }QueueNode; //队列结构 typedef struct Queue{ QueueNode* front; //头 QueueNode* rear; //尾 int size; //队列元素个数 }Queue; //创建队列 Queue* createQueue(){ //申请队列结构内存 Queue* q (Queue*)malloc(sizeof(Queue)); if (q NULL) return NULL; //空队列头尾都初始化为NULL q-front q-rear NULL; q-size 0; return q; } //入队 void enqueue(Queue* q, struct Node* treeNode){ //新建一个队列节点 QueueNode* newNode (QueueNode*)malloc(sizeof(QueueNode)); newNode-treeNode treeNode; newNode-next NULL; //如果队列为空则第一个节点既是头又是尾 if(q-rear NULL){ q-front q-rear newNode; }else{ //队列不为空新节点跟在后面 q-rear-next newNode; q-rear newNode;//更新队尾 } q-size;//队列元素数1 } //出队 struct Node* dequeue(Queue* q){ //队列为空返回NULL if(q-front NULL) return NULL; //先保存队头 QueueNode* temp q-front; //取出树节点 struct Node* treeNode temp-treeNode; //队头往后移动一位 q-front q-front-next; //如果移动完队头为空队尾也为空 if(q-front NULL){ q-rear NULL; } free(temp); q-size--; return treeNode; } int** levelOrder(struct Node* root, int* returnSize, int** returnColumnSizes) { //1.初始化与边界判断 *returnSize 0;//最终有多少层 //当树为空时直接返回 if(root NULL){ *returnSize 0; *returnColumnSizes NULL; return NULL; } //结果二维数组 int **res (int**)malloc(sizeof(int*) * 1000); //存每一层有几个节点 *returnColumnSizes (int*)malloc(sizeof(int) * 1000); //创建队列 Queue* q createQueue(); enqueue(q, root); //2.开始遍历 while(q-size 0){ int levelSize q-size;//当前层有多少节点 int* currentLevel (int*)malloc(sizeof(int) * levelSize); //遍历当前层所有节点 for(int i 0; i levelSize; i){ //出队一个元素 struct Node* currNode dequeue(q); //把值放进当前层数组 currentLevel[i] currNode-val; //把这个节点的孩子依次入队 for(int j 0; j currNode-numChildren;j){ enqueue(q, currNode-children[j]); } } //把这一层存入最终结果 res[*returnSize] currentLevel; //记录这一层有多少节点 (*returnColumnSizes)[*returnSize] levelSize; //层数1 (*returnSize); } free(q); return res; }总结队列的定义创建入队出队存入树的节点数据层序遍历存进结果数组。二.103. 二叉树的锯齿形层序遍历题目描述给你二叉树的根节点root返回其节点值的锯齿形层序遍历。即先从左往右再从右往左进行下一层遍历以此类推层与层之间交替进行。示例 1输入root [3,9,20,null,null,15,7]输出[[3],[20,9],[15,7]]示例 2输入root [1]输出[[1]]示例 3输入root []输出[]解题思路和上一题一样都是层序遍历只是每到下一次需要倒序只需要写一个数组翻转函数每层遍历完取反标记切换遍历方向即可代码描述/** * 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 QueueNode{ struct TreeNode* Node; struct QueueNode* next; }QueueNode; //队列结构体 typedef struct Queue{ QueueNode* front;//头节点 QueueNode* rear;//尾节点 int size;//节点个数 }Queue; //创建队列 Queue* createQueue(){ Queue* q (Queue*)malloc(sizeof(Queue));//开辟空间 //头尾节点均为空 q-rear q-front NULL; q-size 0; return q; } //入队 void enqueue(Queue* q, struct TreeNode* node){ //创建新节点 QueueNode *newNode (QueueNode*)malloc(sizeof(QueueNode)); newNode-Node node; newNode-next NULL; //如果队列为空队头和队尾相同 if(q-front NULL){ q-front q-rear newNode; }else{ //队列不为空将新节点跟在队尾 q-rear-next newNode; q-rear newNode;//队尾更新为新节点 } q-size; } //出队 struct TreeNode* dequeue(Queue* q){ //如果队列为空直接返回空 if(q-front NULL) return NULL; //保存队头 QueueNode* temp q-front; //取出树节点 struct TreeNode* resNode temp-Node; //队头往后一位 q-front q-front-next; //如果移动完队列为空队尾也为空 if(q-front NULL){ q-rear NULL; } //释放temp free(temp); q-size--; return resNode; } //数组翻转用来实现从右往左遍历 void reverseArr(int *arr, int len){ int l 0, r len - 1; while(l r){ int t arr[l]; arr[l] arr[r]; arr[r] t; l; r--; } } int** zigzagLevelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes) { //1.初始化和边界值判断 *returnSize 0; if(root NULL){ *returnSize 0; *returnColumnSizes NULL; return NULL; } //定义结果二维数组 int **res (int**)malloc(sizeof(int*) * 1000); //存每一层有几个节点 *returnColumnSizes (int*)malloc(sizeof(int) * 1000); //创建队列 Queue* q createQueue(); enqueue(q, root); //2.开始遍历 int needReverse 0; while(q-size 0){ int levelSize q-size; int* curLevel (int*)malloc(sizeof(int) * levelSize); //遍历当前层所有节点 for(int i 0; i levelSize; i){ struct TreeNode* cur dequeue(q); curLevel[i] cur-val; //左右孩子依次入队 if(cur-left ! NULL) enqueue(q, cur-left); if(cur-right ! NULL) enqueue(q, cur-right); } //需要反转就翻转当前层数组 if(needReverse 1){ reverseArr(curLevel, levelSize); } //保存当前层结果 res[*returnSize] curLevel; (*returnColumnSizes)[*returnSize] levelSize; (*returnSize); //每层遍历完取反标记切换遍历方向 needReverse !needReverse; } return res; }总结队列的定义创建入队出队存入树的节点数据层序遍历存进结果数组每层遍历完取反标记切换遍历方向。三.662. 二叉树最大宽度题目描述给你一棵二叉树的根节点root返回树的最大宽度。树的最大宽度是所有层中最大的宽度。每一层的宽度被定义为该层最左和最右的非空节点即两个端点之间的长度。将这个二叉树视作与满二叉树结构相同两端点间会出现一些延伸到这一层的null节点这些null节点也计入长度。题目数据保证答案将会在32 位带符号整数范围内。输入root [1,3,2,5,3,null,9]输出4解释最大宽度出现在树的第 3 层宽度为 4 (5,3,null,9) 。示例 2输入root [1,3,2,5,null,null,9,6,null,7]输出7解释最大宽度出现在树的第 4 层宽度为 7 (6,null,null,null,null,null,7) 。解题思路依旧是用队列来进行层序遍历对每一层的节点进行编号每一层的宽度要用right - left 1最后和maxWidth进行比较算出返回maxWidth即可注意宽度不能直接用levelsize q-size来解出因为null也要算入内不能光数节点必须用right - left 1代码描述/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ //队列节点结构体 typedef struct QueueNode{ struct TreeNode* Node; unsigned long long pos; // 编号关键用long long防止溢出 struct QueueNode* next; }QueueNode; //队列结构体 typedef struct Queue{ QueueNode* front;//头 QueueNode* rear;//尾 int size;//队列元素个数 }Queue; //创建队列函数 Queue* createQueue(){ //初始化 Queue* q (Queue*)malloc(sizeof(Queue)); if(q NULL)return NULL; //头尾均为空 q-front q-rear NULL; q-size 0;//队列元素个数为零 return q; } //入队函数 void enqueue(Queue* q, struct TreeNode* Node, unsigned long long pos){ //创建新节点 QueueNode* newNode (QueueNode*)malloc(sizeof(QueueNode)); newNode-Node Node;//给新节点赋值 newNode-pos pos;//给节点编号 newNode-next NULL; //若队列为空则头尾相同直接替换为q if(q-front NULL){ q-rear q-front newNode; }else{ //如果不为空则直接跟在后面 q-rear-next newNode; q-rear newNode;//将尾节点更新 } q-size;//记得更新队列元素长度 } //出队函数 QueueNode* dequeue(Queue* q){ if(q-front NULL)return NULL; //先保存头节点 QueueNode* Temp q-front; //队头往后一位 q-front q-front-next; //如果移动完队列为空队尾也为空 if(q-front NULL){ q-rear NULL; } q-size--; return Temp; } int widthOfBinaryTree(struct TreeNode* root) { //核心思路层序遍历BFS,给每个节点编号每一层记录最左边节点编号和最右边节点编号用left - right 1来定义宽度最后再和maxWidth比较 //1.初始化和边界值判断 if(root NULL)return 0; Queue* q createQueue(); enqueue(q, root, 0);//根节点编号0 unsigned long long maxWidth 0; while(q-size 0){ int levelSize q-size;//存当前层有多少个元素 unsigned long long left 0; unsigned long long right 0; for(int i 0; i levelSize; i){ QueueNode* curr dequeue(q); struct TreeNode* node curr-Node; unsigned long long pos curr-pos; //每层第一个就是最左边 if(i 0) left pos; //每层最后一个就是最右边 if(i levelSize - 1) right pos; //左孩子 if(node-left){ enqueue(q, node-left, pos * 2 1); } //右孩子 if(node-right){ enqueue(q, node-right, pos * 2 2); } free(curr); } //计算当前层宽度 unsigned long long width right - left 1; if(width maxWidth) { maxWidth width; } } return maxWidth; }总结队列层序遍历给每一层的数编号用right - left 1来计算出每一层宽度四.515. 在每个树行中找最大值题目描述给你一棵二叉树的根节点root返回树的最大宽度。树的最大宽度是所有层中最大的宽度。每一层的宽度被定义为该层最左和最右的非空节点即两个端点之间的长度。将这个二叉树视作与满二叉树结构相同两端点间会出现一些延伸到这一层的null节点这些null节点也计入长度。题目数据保证答案将会在32 位带符号整数范围内。示例 1输入root [1,3,2,5,3,null,9]输出4解释最大宽度出现在树的第 3 层宽度为 4 (5,3,null,9) 。示例 2输入root [1,3,2,5,null,null,9,6,null,7]输出7解释最大宽度出现在树的第 4 层宽度为 7 (6,null,null,null,null,null,7) 。示例 3输入root [1,3,2,5]输出2解释最大宽度出现在树的第 2 层宽度为 2 (3,2) 。解题思路队列层序遍历找出每一层最大的数存入结果数组即可代码描述/** * 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(). */ //队列节点结构体 typedef struct QueueNode{ struct TreeNode* Node; struct QueueNode* next; }QueueNode; //队列结构体 typedef struct Queue{ QueueNode* front; QueueNode* rear; int size; }Queue; //创建队列 Queue* createQueue(){ Queue* q (Queue*)malloc(sizeof(Queue)); if(q NULL)return NULL; //空队列头尾都初始化为NULL q-front q-rear NULL; q-size 0; return q; } //入队操作 void enqueue(Queue*q, struct TreeNode* Node){ //新建一个队列节点 QueueNode* newNode (QueueNode*)malloc(sizeof(QueueNode)); newNode-Node Node; newNode-next NULL; //如果队列为空则第一个节点就是头节点和尾节点 if(q-front NULL){ q-front q-rear newNode; }else{ //否则将新节点插入队列尾部 q-rear-next newNode; q-rear newNode;//更新尾节点为新节点 } q-size;//队列大小增加 } //出队操作 struct TreeNode* dequeue(Queue*q){ //如果队列为空返回NULL if(q-front NULL)return NULL; //先保存队头 QueueNode* temp q-front; //取出树节点 struct TreeNode* node temp-Node; //队头往后移动一位 q-front q-front-next; //如果移动完队列为空队尾也为空 if(q-front NULL){ q-rear NULL; } //释放temp free(temp); q-size--; return node; } int* largestValues(struct TreeNode* root, int* returnSize) { //核心思路层序遍历遍历每一层的数进行比较找出最大的数存到结果数组 //1.初始值和边界判断 if(root NULL){ *returnSize 0; return NULL; } //结果数组 int *res (int*)malloc(sizeof(int) * 10000); *returnSize 0; //创建队列 Queue* q createQueue(); enqueue(q, root);//根节点入队 //2.层序遍历 while(q-size 0){ int levelSize q-size;//存当前层有多少元素 int maxNum INT_MIN;//每次找出后存入res,再重置方便下一次寻找 for(int i 0; i levelSize; i){ //遍历当前层找出最大的节点 struct TreeNode* currNode dequeue(q); //直接拿节点值和最大值比 if(currNode-val maxNum){ maxNum currNode-val; } //将左右孩子存在就入队 if(currNode-left ! NULL){ enqueue(q, currNode-left); } if(currNode-right ! NULL){ enqueue(q, currNode-right); } } //将这一层最大的数存入结果数组 res[*returnSize] maxNum; (*returnSize); } free(q); return res; }总结bfs层序遍历二叉树找出每一层最大的数存入结果数组即可