LeetCode·429.N叉树的层次遍历·层次遍历
2023-09-27 14:26:29 时间
题目![](https://img-blog.csdnimg.cn/cc44be225a074c3f983d7fba64f53de1.png)
示例![](https://img-blog.csdnimg.cn/574b1aaec48a469f8b0e35eda135cb5f.png)
思路
解题思路
可以直接使用树的层次遍历摸版,只不过多判断几次子节点即可
代码
/**
* 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().
*/
#define MAX_LEVE_SIZE 1000
#define MAX_NODE_SIZE 10000
int** levelOrder(struct Node* root, int* returnSize, int** returnColumnSizes) {
int ** ans = (int **)malloc(sizeof(int *) * MAX_LEVE_SIZE);
*returnColumnSizes = (int *)malloc(sizeof(int) * MAX_LEVE_SIZE);
if (!root) {
*returnSize = 0;
return ans;
}
struct Node ** queue = (struct Node **)malloc(sizeof(struct Node *) * MAX_NODE_SIZE);//初始化栈
int head = 0, tail = 0;
int level = 0;
queue[tail++] = root;//头结点入栈
while (head != tail) {//层次遍历
int cnt = tail - head;
ans[level] = (int *)malloc(sizeof(int) * cnt);
for (int i = 0; i < cnt; ++i) {
struct Node * cur = queue[head++];
ans[level][i] = cur->val;
for (int j = 0; j < cur->numChildren; j++) {//遍历所以存在的子节点并入栈
queue[tail++] = cur->children[j];
}
}
(*returnColumnSizes)[level++] = cnt;
}
*returnSize = level;
free(queue);
return ans;
}
作者:xun-ge-v
链接:https://leetcode.cn/problems/n-ary-tree-level-order-traversal/solution/-by-xun-ge-v-1632/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
相关文章
- 【Leetcode】107. 二叉树的层序遍历 II(中等)
- [LeetCode] Search Insert Position
- 113、【树与二叉树】leetcode ——538. 把二叉搜索树转换为累加树:递增数组视角右中左遍历(C++版本)
- 105、【树与二叉树】leetcode ——530. 二叉搜索树的最小绝对差:中序遍历递归法+迭代法(C++版本)
- 89、【树与二叉树】leetcode ——101. 对称二叉树:后序递归+迭代法+层次遍历(C++版本)
- leetcode 143
- 【leetcode】107 : 二叉树的层序遍历 II
- 【leetcode】102:二叉树的层序遍历
- [LeetCode] Self Dividing Numbers 自整除数字
- [LeetCode] Set Mismatch 设置不匹配
- [LeetCode] 382. Linked List Random Node 链表随机结点
- [LeetCode] 314. Binary Tree Vertical Order Traversal 二叉树的竖直遍历
- [LeetCode] 57. Insert Interval 插入区间
- [LeetCode] 94. Binary Tree Inorder Traversal 二叉树的中序遍历
- [LeetCode] 103. Binary Tree Zigzag Level Order Traversal 二叉树的之字形层序遍历
- [LeetCode] 106. Construct Binary Tree from Inorder and Postorder Traversal 由中序和后序遍历建立二叉树
- [LeetCode] Triangle 三角形
- [LeetCode] 107. Binary Tree Level Order Traversal II 二叉树层序遍历之二
- Leetcode——17. Letter Combinations of a Phone Number
- leetcode 94. Binary Tree Inorder Traversal 二叉树的中序遍历(中等)