102. 二叉树的层次遍历

Posted on 2019-10-13 In Leetcode , Leetcode TOP 100 Views: Disqus:

LeetCode刷题系列。

描述

给定一个二叉树，返回其按层次遍历的节点值。（即逐层地，从左到右访问所有节点）。

例如:
给定二叉树: [3,9,20,null,null,15,7],

返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

来源：力扣（LeetCode）
链接：102. Binary Tree Level Order Traversal

解题思路

通常，二叉树的层序遍历可以借助队列进行实现，具体的算法实现可以设置一个队列结构，遍历从根节点开始，首先将根节点指针入队，然后开始执行下面三个操作：

从队列中取出一个元素
访问该元素所指节点的值
若该元素所指节点的左、右孩子节点非空，则将其左、右孩子的指针顺序入队

不断执行以上三个步骤，直到队列为空，再无元素可取，二叉树的层序遍历就完成了。

回到本题，首先当然是定义队列结构即相关操作函数，主要有Qinit, push, pop, isFull, isEmpty等等。

具体代码见解法一，代码当中会给出相关注释。

显然，如果用C语言需要自己实现队列，从头开始造轮子，代码比较多，如果使用递归，代码会简洁很多。

递归的主要思路是：传递变量level来表示处在第几层，使用rcs数组存放每层中已经存放了几个元素。采用左子树 ->本节点 ->右子树的遍历顺序，达到从左到右的添加顺序。或者本节点 -> 左子树 ->右子树顺序，左边在右边前面即可。

具体代码见解法二。

代码

解法一：迭代


/**
 * 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 *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */

// 定义队列最大容量
#define QMAX 1024
typedef struct TreeNode* Tree;

typedef struct Queue
{
    // 保存树节点的指针
    Tree Node[QMAX];
    int front;
    int rear;
}Queue;

//队列初始化
void Qinit(Queue *q)
{
    q->front = q->rear = 0;
 
}

//判断队列是否已满
bool isFull(Queue *q)
{
    return ((q->rear + 1) % QMAX == q->front);
}

//判断队列是否为空
bool isEmpty(Queue *q)
{
    return q->rear == q->front;
}

//入队
bool push(Queue *q, Tree node)
{
  
    if(isFull(q))
        return false;
    
    q->Node[q->rear] = node;
    q->rear = (q->rear + 1) % QMAX;
    return true;
}


Tree pop(Queue *q)
{
    if(isEmpty(q))
    {
        return NULL;
    }
    
    Tree node;
    //存储队列头元素
    node = q->Node[q->front];
    q->front = (q->front + 1) % QMAX;
    return node;
}


int** levelOrder(Tree root, int* returnSize, int** returnColumnSizes)
{
    *returnSize = 0;
    //如果树为空则返回NULL
    if (!root){
        return NULL;
    }
    
    Queue queue;
    //使用封装的环形队列进行初始化
    Qinit(&queue);
    
    //每一层节点的个数分配空间并初始化为1，最多有QMAX层
    int *level = (int *)calloc(1, sizeof(int) * QMAX);
    
    //首先将根节点入队
    push(&queue, root);
    
    //控制层序遍历时各层的高度，第一层仅为根节点，高度为0
    int height = 0;
    //初始化各层元素个数，第一层仅为根节点，元素个数为1
    level[height] = 1;
    
    //初始化返回结果，最大有QMAX层，比如二叉树退化成单链表
    int **result = (int **)malloc(sizeof(int *) * QMAX);
    
    //如果队列不空，进入层序遍历的大循环
    while (!isEmpty(&queue)) 
    {   
        //高度+1
        height++; 
        //初始化并分配每一层的元素个数
        result[height - 1] = (int *)malloc(sizeof(int *) * level[height - 1]);
        
        //各层元素的循环输出到result二维表
        for (int i = 0; i< level[height - 1]; i++)
        {   
            //从队列中取出一个元素
            root = pop(&queue);
            //队列数据输入到result二维表
            result[height - 1][i] = root->val;
 
            //如果左孩子非空访问左孩子
            if (root->left)
            {
                push(&queue, root->left);
                //这个很重要，更新层的高度
                level[height]++;
            }
            //如果右孩子非空访问右孩子
            if (root->right)
            {
                push(&queue, root->right);
                level[height]++;
            }
        }
    }

    //每一列的节点数
    *returnColumnSizes = level;
    //返回层数
    *returnSize = height;
 
    return result;
}

解法二：递归

/**
 * 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 *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */

typedef struct TreeNode* Tree;

#define LEV 1024
#define LEN 1024

void get(Tree node, int level, int **ret, int *ret_index, int *rcs)
{
    //如果树为空则返回NULL
    if(!node) return NULL;
    
    if(!ret[level])
    {
        ret[level] = (int *)malloc(sizeof(int) * LEN);
        rcs[level] = 0;
    }
    
    if(level > *ret_index)
    {
        *ret_index = level;
    }
    
     ret[level][rcs[level]++] = node->val; 
    
    get(node->left, level + 1, ret, ret_index, rcs);
  
    get(node->right, level + 1, ret, ret_index, rcs);
  
    
}

int** levelOrder(Tree root, int* returnSize, int** returnColumnSizes)
{
    int **ret = (int **)malloc(sizeof(int*) * LEV);
    int *rcs = (int*)malloc(sizeof(int) * LEV);
    int ret_index = 0;
    
    memset(ret, 0, sizeof(int*) * LEV);
    memset(rcs, 0, sizeof(int) * LEV);
    
    get(root, 0, ret, &ret_index, rcs);
    
    *returnSize = root==NULL ? 0 : ret_index + 1;
    *returnColumnSizes = rcs;
    
    return ret;
}

参考

Leetcode题解里面的其他人的解法
LeetCode-102-二叉树的层次遍历-C语言