队列应用-二（N）叉树的层序遍历/深度

1. 二叉树层序遍历

   
   image.png

要点数据结构：
(1) queue
front, tail
struct treeNode *queue
(2) 层序遍历管理结构
level ==> *returnSize
levelSize ==> *retColumnSize
int **array 层序遍历数组
要点步骤：
(1) 利用queue的基本操作push, pop, 从root 开始逐层push 每一层node 进 queue，每次pop 一层node 作为遍历该层node, 与此同时准备push 其left, right 来准备下一层的遍历 ;
(2) 分层遍历：pop 该层的所有node进queue：
pop 的所有node的取值存到该层数组里；
pop 的node的left 和right node push 进queue;
下一层node 数量：tail - front;

#define MAX_LEVEL (2000)
#define MAX_NODE (2000)
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
    if (root== NULL) {
        *returnSize = 0;
        return NULL;
    }

    int **levelarray=malloc(sizeof(int *) * MAX_LEVEL);
    struct TreeNode **queue=malloc(sizeof(struct TreeNode *) * MAX_NODE);

    int *columeSize = malloc(sizeof(int) * MAX_NODE);
    int front = 0, tail = 0;
    int level = 0;
    int levelsize = 0;

    queue[tail++] = root;
    levelsize = tail - front;

    columeSize[level] = levelsize;
    while(levelsize) {
        int i;
        levelarray[level] = malloc(sizeof(int) * levelsize);
        for(i=0;i<levelsize;i++) {
            struct TreeNode *curNode = queue[front];
            levelarray[level][i] = curNode->val;
            if(curNode->left)
                queue[tail++] = curNode->left;
            if(curNode->right)
                queue[tail++] = curNode->right;            
            front++;
        }
        level++;
        levelsize = tail - front;
        columeSize[level] = levelsize;

    }

    *returnColumnSizes = columeSize;
    *returnSize = level;
    return levelarray;
}

2. 二叉树的深度

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
#define MAX_NODE (10000)

int maxDepth(struct TreeNode* root){
    if (root == NULL)
        return 0;
    struct TreeNode** queue = malloc(sizeof(struct TreeNode*) * MAX_NODE);

    int front = 0, tail = 0;
    int level = 0;
    int levelSize = 0;

    queue[tail++] = root;
    levelSize = tail - front;

    while(levelSize) {
        int i;

        for(i=0;i<levelSize;i++) {
            struct TreeNode* curNode = queue[front++];
            if(curNode->left)
                queue[tail++] = curNode->left;
            if(curNode->right)
                queue[tail++] = curNode->right;
        }

        levelSize = tail - front;
        level++;
    }
    return level;
}

3. N叉树层序遍历

#define MAX_LEVEL (1000)
#define MAX_NODE (10000)
int** levelOrder(struct Node* root, int* returnSize, int** returnColumnSizes) {
    if (root == NULL) {
        *returnSize = 0;
        return NULL;
    }
    int **array = malloc(sizeof(int *) *MAX_LEVEL);
    int *arraySize = malloc(sizeof(int) * MAX_LEVEL);

    int front = 0, tail = 0;
    int level = 0, levelSize = 0;

    struct Node** queue = malloc(sizeof (struct Node*) * MAX_NODE);

    queue[tail++] = root;
    levelSize = tail - front;

    while (levelSize) {
        int i;
        arraySize[level] = levelSize;
        array[level] = malloc(sizeof(int) * levelSize);
        for(i=0;i<levelSize;i++) {
            struct Node* curNode = queue[front++];
            array[level][i] = curNode->val;
            int j;
            for(j=0;j<curNode->numChildren;j++) {
                queue[tail++] = curNode->children[j];
            }

        }
        levelSize = tail - front;
        level++;
    }

    *returnColumnSizes = arraySize;
    *returnSize = level;
    return array;

}

4. N叉树的深度

   
   image.png

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     int numChildren;
 *     struct Node** children;
 * };
 */
#define MAX_NODE (10000)
int maxDepth(struct Node* root) {

    if (root == NULL)
        return 0;
    struct Node**queue = malloc(sizeof(struct Node*) * MAX_NODE);  

    int front = 0, tail = 0;
    int level = 0, levelSize = 0;

    queue[tail++] = root;
    levelSize = tail - front;

    while(levelSize) {

        int i;
        for(i=0;i<levelSize;i++) {

            struct Node* curNode = queue[front++];
            int j;
            for(j=0;j<curNode->numChildren;j++) {
                if(curNode->children[j])
                    queue[tail++] = curNode->children[j];
            }
        }
        levelSize = tail - front;
        level++;
    }

    return level;
}