Why my code crash when my input is odd？

• I just want to know why my code will crash when the deepth is odd, please comment me if you are Interested in this Bug.

UPDATED

`````` class Solution
{
public:
{
//initial
int maxDeep = deepCounter(root);
if(maxDeep == 0)
{
return;
}
//get the counts of each layer
int* lengthOfEachFloor = ElementCounter(maxDeep);
upFloor[0] = root;
upFloor[0]->next = NULL;
if(2 <= maxDeep)
{
doConnect(upFloor, 2, maxDeep, lengthOfEachFloor);
}
delete[] lengthOfEachFloor;
}
//connect each layer
void doConnect(TreeLinkNode** upFloor, int deep, int maxDeep, int* lengthOfEachFloor)
{
//upNum saved the counts of upper layer
int upNum = lengthOfEachFloor[deep - 1];
//nowNum saved the counts of current layer
int nowNum = lengthOfEachFloor[deep];
//nowFloor saved the nodes of current layer
//When the deepth is odd, such as 3,5,7 my code will crash at this line ( I have test it in local ), I do not know why this happen
//put nodes of current layer into nowFloor
for(int i = 0, j = 0; i < upNum; i++, j += 2)
{
nowFloor[j] = upFloor[i]->left;
nowFloor[j + 1] = upFloor[i]->right;
}
//connecting
for(int k = 0; k < nowNum - 1; k++)
{
nowFloor[k]->next = nowFloor[k + 1];
}
nowFloor[nowNum - 1]->next = NULL;
//release the memory of upper layer
delete[] upFloor;
//recurrence
deep++;
if(deep <= maxDeep)
{
doConnect(nowFloor, deep, maxDeep, lengthOfEachFloor);
}
else
{
delete[] nowFloor;
}
}

//return the counts of each layer
int* ElementCounter(int deep)
{
int len = deep + 1;
int* result = new int[len];
result[0] = 0;
result[1] = 1;
for(int i = 2; i < len + 1; i++)
{
result[i] = 2 * result[i - 1];
}
return result;
}

//get deepth of the tree
{
int deep = 0;
while(root != NULL)
{
deep++;
root = root->left;
}
return deep;
}
};``````

1. Retag, use `-` connect word, it should be `runtime-error`.
2. Tell the algorithm in some words.
3. Remove bunch of DEBUG INFO, shorten your code with the exact solution, you submit to OJ.

Thanks.

• Hi! Shangrila, I have refine the code and paste it at next floor, Thank you for your comment and help.

• @Isxaimm, Thanks for your updating. Could you please just edit and update your question post? Because other floors are for answers. You can just cover the original long code. Thanks.

• that's a litter bit complex...
you can try my method

``````    class Solution {
public:

if( NULL==root || (NULL==root->left || NULL==root->right) ) return;

//step 1
if( NULL!=root->left && NULL!=root->right )
{
root->left->next=root->right;
connect(root->left);
connect(root->right);
}

//step 2
while( NULL!=lRoot->right && NULL!=rRoot->left )
{
lRoot->right->next=rRoot->left;
lRoot=lRoot->right;
rRoot=rRoot->left;
}
}
};``````

• Thank your help and comment, h4breeze! I have the easy way to solve this problem, But I just want to find out why this code can not work will.

• @Shangrila, Thanks for you reply, And when I see this I find you have done eveything. You are very kind. Thank you.

• Have no idea why it throws runtime error on the line you marked.

I find a bug in here, after fix it, it will pass.

``````    //return the counts of each layer
int* ElementCounter(int deep)
{
int len = deep + 1;
int* result = new int[len];
result[0] = 0;
result[1] = 1;
for(int i = 2; i < len + 1; i++)     // should be i < len, since only new int[len], result[i] will out of range
{
result[i] = 2 * result[i - 1];
}
return result;
}``````

• @Shangrila, Thanks!! I see your answer just now. That is really a stupid mistake! After fix it my code can pass this test, Thank you for your great help!! And by the way how did you find this bug? I was so confused by the error "malloc.c:2451" at the line I marked before you find this. But now I think I can find out the reason. Thanks for you help again!

• When I debug code, I prefer read it, just like read poem and run it in my brain. =) As such mistake you made, more like a 'typo', I think reading code is much easier to find out than debug tools.

• OK, :) When next time I have a problem I will use your method.

• "You may only use constant extra space." so does that mean you cannot use recursion?

• @qingdihaian, yes, recursion will have extra space, depend on the level of tree.

• Another nice method:

``````void connect(TreeLinkNode *root) {

if (NULL == root) {
return;
}

/* set the next pointer for his left child */
if (NULL != left) {
left->next = right;
}

/* set the next pointer for his right child */
if (NULL != right && NULL != root->next) {
right->next = root->next->left;
}

/* do it recursively */
connect(left);
connect(right);
}``````

• This is a brilliant solution :)

• if deep = 0, this code may crash. better to do a check even if you know it is impossible to be zero.

• Looks pretty go, thx

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.