leetcode刷题笔记（四）

第102题 二叉树的层序遍历

输入： [3,9,20,null,null,15,7] 输出： [ [3], [9,20], [15,7] ]

总体思路是用一个队列， 1.第一层的结点先入队，访问第一层节点的值域，存入二维数组r[][] 2.再将该结点的左右子树依次入队 重复以上操作，直到遍历完全部结点。

和之前的题目一样，采用循环队列，以及头尾指针front和rear。每遍历一层之后，front指向上一层的最后一个元素，rear指向当前层的最后一个元素。 用lev记录层号，cur记录当前层的结点个数。

#define maxsize 1000 int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){ struct TreeNode * queue[maxsize], *p; int front = 0; int rear = 0; //空树 if(!root){ *returnSize = 0; return NULL; } //申请一个二维数组存储层次遍历结果 int **r = malloc(sizeof(int*) * maxsize); * returnColumnSizes = malloc(sizeof(int) * maxsize); //层号和当前层的结点个数 int lev = 0; int cur; //根结点入队 rear = (rear+1)%maxsize; queue[rear] = root; while(front!=rear){ cur = (rear - front + maxsize) % maxsize;//当前层结点个数 (*returnColumnSizes)[lev] = cur; r[lev] = malloc(sizeof(int)*maxsize); // for(int i=0; i<cur; i++){ front = (front+1) % maxsize; p = queue[front]; r[lev][i] = p->val; if(p->left){ rear = (rear+1) % maxsize; queue[rear] = p->left; } if(p->right){ rear = (rear+1) % maxsize; queue[rear] = p->right; } } lev++; } *returnSize = lev; return r; }

103题，二叉树锯齿层序遍历 输出：

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

需要分奇数层和偶数层进行讨论。size为当前层元素个数 对于奇数层的元素，从size-1位置开始存；偶数则从0号位置开始存

#define maxsize 1000 int** zigzagLevelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){ struct TreeNode *queue[maxsize], *p; int front = 0; int rear = 0; if(!root){ *returnSize = 0; return NULL; } int **r = malloc(sizeof(int*) * maxsize); * returnColumnSizes = malloc(sizeof(int) * maxsize); int lev = 0; queue[rear] = root; rear = (rear+1)%maxsize; while(rear!=front){ int size=rear>front?(rear-front):(rear-front+maxsize); (*returnColumnSizes)[lev]=size; r[lev]=malloc(sizeof(int)*size); int i=0; while(size){ p = queue[front]; front = (front+1) % maxsize; if(lev%2==0) r[lev][i++]=p->val; else r[lev][size-1]=p->val; if(p->left){ queue[rear]=p->left; rear = (rear+1) % maxsize; } if(p->right){ queue[rear]=p->right; rear = (rear+1) % maxsize; } size--; } lev++; } *returnSize = lev; return r; }