题目描述
从上往下打印出二叉树的每个结点,同一层的结点按照从左到右的顺序打印。
样例
输入如下图所示二叉树[8, 12, 2, null, null, 6, null, 4, null, null, null]
8
/ \
12 2
/
6
/
4
输出:[8, 12, 2, 6, 4]
算法1
时间复杂度
参考文献
C 代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* Return an array of size *returnSize.
* Note: returned array must be malloced, assume caller calls free().
*/
typedef struct Node{
struct TreeNode * data;
struct Node *next;
}List;
typedef struct{
List *front,*rear;
int size;
}SQueue,*SQlist;
void ADD(struct TreeNode *root,SQlist L){
List *p =(List *)malloc(sizeof(List));
p->data=root;
p->next=NULL;
L->rear->next=p;
L->rear=p;
L->size++;
}
int* printFromTopToBottom(struct TreeNode* root , int* returnSize){
int *a=(int*)malloc(sizeof(int)*1000);
int i=0;
SQueue L;
L.size=0;
L.front=L.rear=(List *)malloc(sizeof(List));
(L.front)->next=NULL;//初始化一个带头结点的链队列
List *p=(List *)malloc(sizeof(List));
if(root==NULL){
*returnSize=0;//返回数组长度
return a;
}
p->data=root;p->next=NULL;
( L.rear)->next=p;
( L.rear)= p;
L.size++;
while(L.size){
(L.front)=(L.front)->next;
if((L.front)->data!=NULL){
a[i++]=(L.front)->data->val;
if((L.front)->data->left!=NULL) ADD((L.front)->data->left,&L);
if((L.front)->data->right!=NULL) ADD((L.front)->data->right,&L);
}
L.size--;
}
*returnSize=i;
return a;
}