[987] Vertical Order Traversal of a Binary Tree (TBD)

搞錯題意了 囧

寫出了一個屍體><  

如果題目改成同一個row的都要sorting的話～那就是以下的版本 （被毆飛）

我需要冷靜一下XD 先這樣就好 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 *returnColumnSizes array.

* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().

*/

int comp(const void *a, const void *b){

return (*(int*)a-*(int*)b);

}

// shift (0,0) to (0, 512/2) to make (-1) can be covered.

#define SHIFT 256

#define RET_R 512

#define RET_C 10 //(20 if 重疊？！)

void initMatrix(struct TreeNode* root, int** ret , int r, int c ,int* idx) {

if (root == NULL)

return;

//printf("%d %d %d\n", root->val , r, c-SHIFT);

ret[c][(idx[c])++]= root->val;

int org = idx[c];

initMatrix(root->left , ret , r+1, c-1, idx);

initMatrix(root->right , ret , r+1, c+1, idx);

// (idx[c] - org)

//for (int i=0; i<idx[c]; i++)

//printf("!!! %d %d\n", ret[c][i], idx[c]);

qsort(ret[c]+org,(idx[c] - org), sizeof (int),comp);

return;

}

int** verticalTraversal(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {

*returnSize = RET_R;

int **ret = calloc ( *returnSize, sizeof (int*));

int *idxs = calloc ( *returnSize, sizeof (int));

(*returnColumnSizes) = calloc (*returnSize, sizeof (int));

for (int i=0; i<*returnSize; i++){

ret[i] = calloc (RET_C, sizeof (int));

ret[i][0] = -1;

}

initMatrix(root,ret, 0,0+SHIFT, idxs);

int size = 0;

for (int i=0; i<*returnSize; i++)

{

if (ret[i][0]<0)

continue;

qsort(ret[i],idxs[i], sizeof (int),comp);

memcpy(ret[size], ret[i] , sizeof(int)*idxs[i]);

(*returnColumnSizes)[size++]= idxs[i];

}

*returnSize =size;

return ret;

}

如果有一天～（梁靜茹上身）
改好的版本放下面(?)

ps. 看來三維陣列是跑不掉了～偷看解答是 用含row跟 column的linked list 去解