先貼一下out of memory的版本 XD 之後再來改可以過的版本吧QQ (更新在後面）
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
int get_level(struct TreeNode* root, int level){
if (root == NULL)
return level;
int left = get_level (root->left , level+1);
int right = get_level (root->right , level+1);
return (left>right)?(left):(right);
}
void traverse(struct TreeNode* root, int level, int** queue, int *idx){
if (root == NULL)
return ;
queue[level][idx[level]] = root->val ;
idx[level]+=1;
traverse (root->left , level+1, queue, idx);
traverse (root->right , level+1, queue, idx);
}
bool isEvenOddTree(struct TreeNode* root) {
int maxnum = get_level(root, 0);
int **queue = calloc (maxnum, sizeof (int*));
int *idx = calloc (maxnum, sizeof (int));
for (int i=0; i<maxnum; i++)
{
queue[i] = calloc (pow(2,i), sizeof(int));
}
traverse(root, 0, queue, idx);
bool ret = true;
for (int i=0; i<maxnum; i++)
{
bool even = (i%2 == 0);
for (int j=0; j<idx[i]; j++)
{
if (((even) && queue[i][j]%2 == 0) || ((!even) && queue[i][j]%2 != 0))
{
ret = false;
break;
}
else if (j== idx[i]-1)
{
continue;
}
else if (even)
{
if (queue[i][j+1] <=queue[i][j])
{
ret = false;
break;
}
}
else if (!even)
{
if (queue[i][j+1] >= queue[i][j])
{
ret = false;
break;
}
}
}
}
for (int i=0; i<maxnum; i++)
{
free(queue[i]);
}
free (queue);
return ret;
}
人生好難喔嗚嗚嗚嗚
寫好queue的寫法之後，速度真慢XD
看來 ％2 還是少做為妙～重新排列了一下判斷式之後有變快一點點。
原本的code 也留著，雖然看起來有一點醜 QQ
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
bool isEvenOddTree(struct TreeNode* root) {
#if 0
struct TreeNode** queue = calloc (100000 , sizeof(struct TreeNode*));
for (int i=0; i<100000; i++)
queue[i]= calloc (1, sizeof(struct TreeNode));
#else
struct TreeNode* queue[100000];
#endif
int start = 0;
int end = 1;
int level = 0;
queue[start]= root;
while (end - start > 0)
{
int idx = end;
for (int i = start; i< end; i++)
{
#if 1
if (level%2 == 0 )
{
if (queue[i]->val %2 ==0)
return false;
if ((i < end-1 ) &&(queue[i]->val >= queue[i+1]->val))
return false;
}
else
{
if (queue[i]->val %2 !=0)
return false;
if ((i < end-1 ) &&(queue[i]->val <= queue[i+1]->val))
return false;
}
#else
if ((level%2 == 0 && queue[i]->val %2 ==0) ||
(level%2 != 0 && queue[i]->val %2 !=0))
return false;
else if (level%2 == 0 && i < end-1)
{
if (queue[i]->val >= queue[i+1]->val)
return false;
}
else if (level%2 != 0 && i < end-1)
{
if (queue[i]->val <= queue[i+1]->val)
return false;
}
#endif
if (queue[i]->left != NULL)
queue[idx++] = queue[i]->left;
if (queue[i]->right != NULL)
queue[idx++] = queue[i]->right;
}
start = end;
end = idx;
level++;
}
return true;
}
沒有留言:
張貼留言