My 8ms solution using c


  • 0
    M
    void levelNumbersOfTree(struct TreeNode* root, int *levelCount, int level)
    {
    if (!root)
        return;
    levelCount[level]++;
    levelNumbersOfTree(root->left, levelCount, level+1);
    levelNumbersOfTree(root->right, levelCount, level+1);
    }
    
    int levelTraversal(struct TreeNode* root, int **levelNumbers, int n, int **columnSizes)
    {
    if (!root) return 0;
    int count = 0;
    int tail = 1;
    n = 65534;
    struct TreeNode **treeArray = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * (n + 1));
    for (int i = 0; i < n+1; i++) treeArray[i] = NULL;
    treeArray[count] = root;
    int k = 0;
    while (treeArray[count]){
        levelNumbers[k] = (int*)malloc(sizeof(int) * (*columnSizes)[k]);
        for (int j = 0; j < (*columnSizes)[k]; j++){
            levelNumbers[k][j] = treeArray[count]->val;
            if (treeArray[count]->left){
                treeArray[tail] = treeArray[count]->left;
                tail = (tail + 1) % (n+1);
            }
           if (treeArray[count]->right){
                treeArray[tail] = treeArray[count]->right;
                tail = (tail + 1) % (n+1);
            }
            treeArray[count] = NULL;
            count = (count + 1) % (n+1);
        }
        k++;
    }
     free(treeArray);
    return tail;
    }
    
    int depthOfTree(struct TreeNode* root)
    {
    if (root == NULL)
        return 0;
    
    int dleft = depthOfTree(root->left) + 1;
    int dright = depthOfTree(root->right) + 1;
    
    return dleft > dright ? dleft : dright;
    }
    
    
    int** levelOrder(struct TreeNode* root, int** columnSizes, int* returnSize) {
    if (root == NULL) return NULL;
    *returnSize = depthOfTree(root);
    *columnSizes = (int *)malloc(sizeof(int) * (*returnSize));
    int** levelNumbers = (int**)malloc(sizeof(int*) * (*returnSize));
    for (int i = 0; i < *returnSize; i++){
        (*columnSizes)[i] = 0;
     }
    levelNumbersOfTree(root, *columnSizes, 0);
    
    int length = levelTraversal(root ,levelNumbers, pow(2.0, *returnSize-1), columnSizes);
    
    return levelNumbers;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.