把二叉树打印成多行

C 解法, 执行用时: 2ms, 内存消耗: 336KB, 提交时间: 2021-06-03

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

#include <stdbool.h>
#include <stdlib.h>

#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)

/***********************************************/
#define FIFO_TYPE struct TreeNode *
struct fifo_s {
        FIFO_TYPE *buffer;
        int rd;      // position to read
        int wr;      // position to write
        int size;
};

#define FIFO_IS_EMPTY(p)  ( (p)->wr == (p)->rd )
#define FIFO_IS_FULL(p)   ( ((p)->wr - (p)->size) == (p)->rd )

#define FIFO_PUT(p, d)    do { if (!FIFO_IS_FULL(p)) {p->buffer[(p->wr++) % (p)->size] = d;} } while(0)
#define FIFO_GET(p, d)    do { *d = p->buffer[(p->rd++) % (p)->size]; } while(0)
#define FIFO_COUNT(p)     ( (p)->wr - (p)->rd )

struct fifo_s *fifoInit(int size) {
        struct fifo_s *p = (struct fifo_s *)malloc(sizeof(struct fifo_s));
        p->buffer = (FIFO_TYPE*)malloc(sizeof(FIFO_TYPE) * size);
        p->wr = p->rd = 0;
        p->size = size;
        return p;
}

void fifoDeinit(struct fifo_s *p) {
        free(p->buffer);
        p->buffer = NULL;
        free(p);
}

/***********************************************/

int *fillLayer(struct fifo_s *layer) {
    int size = FIFO_COUNT(layer);
    int *buf = (int *)malloc(sizeof(int *) * size);
    struct TreeNode *d;
    for (int i = 0; i < size; i++) {
        FIFO_GET(layer, &d);
        buf[i] = d->val;
    }
    return buf;
}

/**
 * 
 * @param pRoot TreeNode类 
 * @return int整型二维数组
 * @return int* returnSize 返回数组行数
 * @return int** returnColumnSizes 返回数组列数
 */
int** Print(struct TreeNode* pRoot, int* returnSize, int** returnColumnSizes ) {
    // write code here
    int **output = (int **)malloc(sizeof(int *) * 100);
    int *columnSizes = (int *)malloc(sizeof(int) * 100);
    int layerCnt = 0;
    struct fifo_s *f = fifoInit(1000);
    struct fifo_s *layer = fifoInit(100);
    int remains = 0;
    int next = 0;
    struct TreeNode *tmp;
    
    FIFO_PUT(f, pRoot);
    remains++;
    while (!FIFO_IS_EMPTY(f)) {
        FIFO_GET(f, &tmp);
        remains--;
        if (likely(tmp)) {
            FIFO_PUT(layer, tmp);
            FIFO_PUT(f, tmp->left);
            FIFO_PUT(f, tmp->right);
            next += 2;
        }
        if (unlikely(remains == 0 && FIFO_COUNT(layer) > 0)) {
            remains = next;
            next = 0;
            columnSizes[layerCnt] = FIFO_COUNT(layer);
            output[layerCnt] = fillLayer(layer);
            layerCnt++;
        }
    }
    
    *returnSize = layerCnt;
    *returnColumnSizes = columnSizes;
    fifoDeinit(f);
    fifoDeinit(layer);
    return output;
}

C 解法, 执行用时: 2ms, 内存消耗: 352KB, 提交时间: 2021-05-11

#include <stdbool.h>


#define NUL  NULL
#define N    1009 // 10007
#define doNothing


typedef struct Queue {
    int         size;
    int         head;
    const void *array[N];
} Queue;


static const void *
addQueue( Queue *queue, const void *data ) {
    return queue->array[(queue->head + queue->size++) % N] = data;
}

static const void *
pollQueue( Queue *queue ) {
    queue->head = (queue->head + 1) % N;
    --queue->size;

    return queue->array[(queue->head - 1 + N) % N];
}

static int
sizeQueue( const Queue *queue ) {
    return queue->size;
}

static bool
emptyQueue( const Queue *queue ) {
    return queue->size < 1 ? true : false;
}

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

/**
 * 
 * @param pRoot TreeNode类 
 * @return int整型二维数组
 * @return int* returnSize 返回数组行数
 * @return int** returnColumnSizes 返回数组列数
 */
extern int**
Print( struct TreeNode *root, int *returnSize, int **returnColumnSizes ) {
    int **answer = NUL;
    int *column = NUL;
    Queue queue = {0, 0, {NUL}};
    
    *returnSize = 0;
    answer = (int **) malloc( N * sizeof(int *) );
    *returnColumnSizes = column = (int *) malloc( N * sizeof(int) );
    if( root != NUL ) {
        addQueue( &queue, root );
    }
    for( ; !emptyQueue( &queue ); ) {
        answer[*returnSize] = (int *) malloc( sizeQueue( &queue ) * sizeof(int) );
        column[*returnSize] = 0;
        for( int i = sizeQueue( &queue ); --i >= 0; ) {
            root = (struct TreeNode *) pollQueue( &queue );
            answer[*returnSize][column[*returnSize]++] = root->val;
            if( root->left != NUL ) {
                addQueue( &queue, root->left );
            }
            if( root->right != NUL ) {
                addQueue( &queue, root->right );
            }
        }
        ++returnSize[0];
    }
    
    return answer;
}

C++ 解法, 执行用时: 2ms, 内存消耗: 356KB, 提交时间: 2021-03-03

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    vector<vector<int>> res;
    vector<vector<int> > Print(TreeNode* pRoot) {
        if (NULL == pRoot) {
            return res;
        }
        queue<TreeNode*> q;
        q.push(pRoot);
        while (!q.empty()) {
            int sz = q.size();
            vector<int> tmp;
            for (int i=0; i<sz; i++) {
                TreeNode* t = q.front();
                tmp.push_back(t->val);
                q.pop();
                if (i == sz-1) {
                    res.push_back(tmp);
                }
                if (t->left) {
                    q.push(t->left);
                }
                if (t->right) {
                    q.push(t->right);
                }
            }
        }
        return res;
    }
    
};

C++ 解法, 执行用时: 2ms, 内存消耗: 356KB, 提交时间: 2020-09-12

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
        vector<vector<int> > Print(TreeNode* pRoot) {
            
            vector<vector<int>> result;
            if(pRoot == nullptr)
                return result;
            
            queue<TreeNode*> q;
            q.push(pRoot);
            while(q.size() != 0)
            {
                int  n= 0; //每层元素数(从0计数)
                int qSize = q.size();
                vector<int> oneLeve;
                while(n++ < qSize){
                    TreeNode* temp = q.front();
                    q.pop();
                    oneLeve.push_back(temp->val);
                    if(temp->left != nullptr)
                        q.push(temp->left);
                    if(temp->right != nullptr)
                        q.push(temp->right);
                }
                
                result.push_back(oneLeve);
            }
            return result;
        }
    
};

C 解法, 执行用时: 2ms, 内存消耗: 356KB, 提交时间: 2020-09-07

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

/**
 * 
 * @param pRoot TreeNode类 
 * @return int整型二维数组
 * @return int* returnSize 返回数组行数
 * @return int** returnColumnSizes 返回数组列数
 */

#define MAXS 1000

int** Print(struct TreeNode* pRoot, int* returnSize, int** returnColumnSizes ) {
    int **res = (int**)malloc(sizeof(int*) * MAXS);
    *returnSize = 0;
    
    if (pRoot == NULL)
        return NULL;
    
    *returnColumnSizes = (int *)malloc(MAXS * sizeof(int));
    struct TreeNode * queue[MAXS];
    int tail = 0;
    int head = 0;
    int size;
    queue[tail++] = pRoot;
    
    while(head < tail){
        size = tail - head;
        (*returnColumnSizes)[*returnSize] = size;
        res[*returnSize] = (int *)malloc(sizeof(int) * size);
        for (int i = 0; i <size; i++){
            struct TreeNode* temp = queue[head++];
            res[*returnSize][i] = temp->val;
            if(temp->left) queue[tail++] = temp->left;
            if(temp->right) queue[tail++] = temp->right;
        }
        (*returnSize)++;
    }
    return res;
    
}

详情