题目

 

示例

 

思路

解题思路

可以直接使用树的层次遍历摸版，只不过多判断几次子节点即可

代码

/**
 * 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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。