LEET code -- Binary Tree Level Order Traversal

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,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

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

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

這題用C有夠痛苦

要自己寫queue

還要注意裡面的**columnSizes 要跟returnSize一樣
外面一定式
int *columnSize;
他傳進來式&columnSize
所以他起始的記憶體式存在的

所以不能columnSize=malloc(sizeof(int *));   這樣會變成宣告一堆int *陣列

每次while 要先看裡面queue的長度 (代表每一階層擁有的個數)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68

/** * 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(). */ void queuePush(struct TreeNode** queue,int *queuesize, int *queueTail, struct TreeNode* element){ queue[(*queueTail)++]=element; (*queuesize)++; // printf("push %d",*queuesize); //if(queuesize>128)queuesize%=128; } struct TreeNode* queuePop(struct TreeNode** queue,int *queuesize,int *queueHead){ int temp=*queueHead; (*queuesize)--; (*queueHead)++; // if(*queueHead==128)*queueHead=0; return queue[temp]; } int** levelOrder(struct TreeNode* root, int** columnSizes, int* returnSize) { //the columnSize is like returnSize, the caller allocate a array pointer //BFS use queue, and need reverse //int max=128; if(root==NULL)return NULL; *returnSize=0; int BFSmax=128; int ** BFS=malloc(sizeof(int*)*BFSmax); *columnSizes=malloc(sizeof(int)*BFSmax); int BFSsize=0;//max 128 struct TreeNode** queue=malloc(sizeof(struct TreeNode*)); int queuesize=0,queueHead=0,queueTail=0; queuePush(queue,&queuesize,&queueTail,root); while(queuesize!=0){ int length=queuesize; if(*returnSize > BFSmax*0.8){ BFSmax*=2; BFS=realloc(BFS,sizeof(int*)*BFSmax); *columnSizes=realloc(*columnSizes,sizeof(int)*BFSmax); } queue=realloc(queue,sizeof(struct TreeNode*)*(length*2+1+queueTail)); int *value=malloc(sizeof(int)*length); //int *valuesize=malloc(sizeof(int)); //*valuesize=length; for(int i=0;i<length;i++){ struct TreeNode * temp=queuePop(queue,&queuesize,&queueHead); value[i]=temp->val; if(temp->left)queuePush(queue,&queuesize,&queueTail,temp->left); if(temp->right)queuePush(queue,&queuesize,&queueTail,temp->right); //printf("leng:%d value:%d size%d ",length,temp->val,queuesize); } BFS[*returnSize]=value; (*columnSizes)[(*returnSize)++]=length; printf("%d ",queuesize); } //printf("%d %d",BFS[1][0],*columnSizes[1]); return BFS; }