二叉树的层次遍历
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
这个题的难点并不在于层次遍历，层次遍历一个队列就足够了，难道在于需要按层次进行存储，我一开始的时候，一直用了一个二维数组，结果内存超过限制，因为事实上每一次的节点数很不同，所以不能直接设置固定的。
C语言代码
/**
* 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 *columnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
#define SIZE 999
int** levelOrder(struct TreeNode* root, int** columnSizes, int* returnSize) {
int **result = (int **)malloc(sizeof(int* )*SIZE);
struct TreeNode *queue[SIZE]; //定于队列
int rear = 0;
int head = 0; // 首位开始都在0，此时为空
int *key = (int*)malloc(sizeof(int)*SIZE);
memset(key,0,sizeof(int)*SIZE);
if(root == NULL)
return NULL;
queue[rear] = root;
rear = (rear + 1) % SIZE;
int height = 0;
key[height] += 1;
while(head != rear){
height += 1;
int i = 0;
printf("malloc: %d ",key[height-1]);
result[height-1] = (int *)malloc(sizeof(int) * key[height-1]);
printf("%d %d
",head,rear);
while(i < key[height-1]){
printf("debug");
root = queue[head];
head =(head + 1) % SIZE;
result[height-1][i++] = root->val;
if(root->left){
queue[rear] = root->left;
rear = (rear + 1) % SIZE;
key[height] += 1;
}
if(root->right){
queue[rear] = root->right;
rear = (rear + 1) % SIZE;
printf("height: %d", height);
key[height] += 1;
}
}
}
printf("last");
*columnSizes = key;
*returnSize = height;
return result;
}