莫再提 T__T
有機會的話用add queue的方式寫一次看看 QQ
/**
* 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().
*/
int** levelOrder(struct TreeNode* root, int** columnSizes, int* returnSize) {
struct TreeNode *queue[10000];
int i=0;
int **retArray = malloc(sizeof(int *)*10000);
*columnSizes = malloc(sizeof(int *)*10000);
*returnSize=0;
if(root == NULL)
return retArray;
struct TreeNode* ptr = root;
int head=0;
int tail=1;
queue[head]= root;
int level = 0;
int nextcount = 0, cur_count=1;
while(head < tail/*ptr != NULL*/)
{
retArray[level] = malloc(sizeof(int) * 10000);
for (i=0;i<cur_count && head < tail;i++)
{
if(ptr->left!=NULL)
{
queue[tail++]=ptr->left;
nextcount++;
}
if(ptr->right!=NULL)
{
queue[tail++]=ptr->right;
nextcount++;
}
retArray[level][i] = ptr->val;
ptr = queue[++head];
}
(*columnSizes)[level++] = cur_count;
cur_count = nextcount;
nextcount = 0;
}
*returnSize=level;
return retArray;
}
20240616 更新
這個寫的好漂亮喔QQ
但pointer 之間的傳遞怎麼那麼麻煩啊哈哈（乾笑）
結果還是沒有用queue 來寫(?)
/**
* 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 *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
int dfs(struct TreeNode* root, int cur)
{
if (root == NULL)
return cur;
int left = dfs(root->left , cur +1);
int right = dfs(root->right , cur +1);
return (left > right) ? (left):(right);
}
void bfs(struct TreeNode* root,int **ret,int *column, int level)
{
if (root== NULL)
return;
ret[level][column[level]] = root->val;
(column[level])++;
bfs(root->left,ret, column, level+1);
bfs(root->right,ret, column, level+1);
}
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {
int depth= dfs(root,0);
int **ret = calloc (depth, sizeof(int*));
(*returnColumnSizes) = calloc (depth, sizeof(int));
for (int i=0; i<depth; i++)
ret[i] = calloc (1024, sizeof(int));
bfs(root,ret,(*returnColumnSizes),0);
*returnSize = depth;
return ret;
}
再次更新，原來是有用queue寫XD 只是寫的不美麗（？）
既然都想要先求個深度（高度）了，就順便算一下有幾個node 好了 XD
然後克服了 : 是pointer array 的queue，指向每個node，還有每個 level 要去紀錄它們有幾個node之後，突然覺得自己的queue寫的很漂亮吶！！！（哈哈哈大頭症笑）我又感受到自己的進步了，我要哭了嗚嗚嗚嗚嗚嗚
/**
* 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 *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
int dfs(struct TreeNode* root, int cur, int *count)
{
if (root == NULL)
return cur;
(*count) +=1;
int left = dfs(root->left , cur +1, count);
int right = dfs(root->right , cur +1, count);
return (left > right) ? (left):(right);
}
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {
if (root == NULL)
{
*returnSize = 0;
return NULL;
}
int count=0;
int depth= dfs(root,0, &count);
int **ret = calloc (depth,sizeof(int*));
(*returnColumnSizes) = calloc (depth, sizeof(int));
for (int i=0; i< depth; i++)
ret[i] = calloc (count/2+1, sizeof(int));
struct TreeNode** queue= calloc (count+1, sizeof(struct TreeNode*));
int start=0, end=1,level=0,idx=0;
queue[idx++] = root;
while (start < end)
{
for (int i=start; i<end;i++)
{
struct TreeNode* ptr = queue[i];
ret[level][(*returnColumnSizes)[level]]=ptr->val;
(*returnColumnSizes)[level]++;
if (ptr->left != NULL)
queue[idx++] = ptr->left;
if (ptr->right != NULL)
queue[idx++] = ptr->right;
}
start = end;
end = idx;
level++;
}
*returnSize = depth;
return ret;
}
沒有留言:
張貼留言