二叉树（层次遍历 C语言）LeetCode（102. 107.）

层次遍历 用队列进行层次遍历（BFS） void Level(BiTree T){ Initqueue(q); BiTree p; Enqueue(q,T); while(!Empty(q)){ Dequeue(q,p); visit(p); if(p->left) Enqueue(q,p->left); if(p->right) Enqueue(q,p->right); } }

#define max 1000 int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){ if(!root){ *returnSize=0; return ; } struct TreeNode *queue[max],*p; int front=0,rear=0; int **r=malloc(sizeof(int*)*max); *returnColumnSizes=malloc(sizeof(int)*max); int lev=0,count=0; rear=(rear+1) % max; queue[rear]=root; while(front!=rear){ count=(rear-front+max) % max; (*returnColumnSizes)[lev]=count; r[lev]=malloc(sizeof(int)*count); for(int i=0;i<count;i++){ front=(front+1)% max; p=queue[front]; r[lev][i]=p->val; if(p->left){ rear=(rear+1) % max; queue[rear]=p->left; } if(p->right){ rear=(rear+1) % max; queue[rear]=p->right; } } lev++; } *returnSize=lev; return r; }

int** levelOrderBottom(struct TreeNode* root, int* returnSize, int** returnColumnSizes){ if (!root){ *returnSize = 0; return NULL; } int rear=0,front=-1,num,top,**ans,*q,*temp1,temp2; struct TreeNode **queue; queue = (struct TreeNode**)malloc(sizeof(struct TreeNode*)*10000);//其实可以先算一下树的深度再开内存，C语言省事就这样了 ans = (int**)malloc(sizeof(int*)*10000); q = (int*)malloc(sizeof(int)*10000); queue[rear] = root; top = -1; while(rear!=front){ ans[++top] = (int*)malloc(sizeof(int)*(rear-front)); q[top] = rear - front; for (int i=front+1;i<=rear;i++) ans[top][i-front-1] = queue[i]->val; num = 0; for (int i=front+1;i<=rear;i++){ if (queue[i]->left) queue[rear+(++num)] = queue[i]->left; if (queue[i]->right) queue[rear+(++num)] = queue[i]->right; } front = rear; rear += num; } for (int i=0;i<(top+1)/2;i++){ temp1 = ans[i]; ans[i] = ans[top-i]; ans[top-i] = temp1; temp2 = q[i]; q[i] = q[top-i]; q[top-i] = temp2; } *returnSize = top+1; *returnColumnSizes = q; return ans; }