C solution using DFS and postfix traversal (not reverse)


  • 3
    C

    Compare to Binary Tree Level Order Traversal which was resovled using prefix traversal, this just the postfix case.

    (My solution of Binary Tree Level Order Traversal: https://discuss.leetcode.com/topic/59106/c-solution-using-dfs)

    But, if want to using postfix traversal, we need to know the max depth in advance, so it seems that I have to do an extra traversal to get the max depth

    /**
     * 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 *columnSizes array.
     * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
     */
    
    void traverse(struct TreeNode *root, int depth, int ***arr, int **columnSizes, int *returnSize)
    {
        int     idx;
        
        if (!root) return;
    
        traverse(root->left, depth + 1, arr, columnSizes, returnSize);
        traverse(root->right, depth + 1, arr, columnSizes, returnSize);
        
        idx = *returnSize - depth - 1;
        (*arr)[idx] = realloc((*arr)[idx], ((*columnSizes)[idx] + 1) * sizeof(int));
        (*arr)[idx][(*columnSizes)[idx]] = root->val;
        ++(*columnSizes)[idx];
    }
    
    void maxdepth(struct TreeNode *root, int depth, int ***arr, int **columnSizes, int *returnSize)
    {
        if (!root) return;
    
        if (*returnSize < depth + 1) {
            *returnSize = depth + 1;
            
            /*
             * Should initialise the one more allocated space to NULL (or 0)
             */
            *arr = realloc(*arr, (depth + 1) * sizeof(int *));
            (*arr)[depth] = NULL;
        
            *columnSizes = realloc(*columnSizes, (depth + 1) * sizeof(int));
            (*columnSizes)[depth] = 0;
        }
        
        maxdepth(root->left, depth + 1, arr, columnSizes, returnSize);
        maxdepth(root->right, depth + 1, arr, columnSizes, returnSize);
    }
    
    
    int** levelOrderBottom(struct TreeNode* root, int** columnSizes, int* returnSize) {
        int **arr;
        
        arr = NULL;
        *returnSize = 0;
        maxdepth(root, 0, &arr, columnSizes, returnSize);
        traverse(root, 0, &arr, columnSizes, returnSize);
        
        return arr;
    }
    

Log in to reply
 

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