Why my code crash when my input is odd?


  • 0
    L

    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
    clean code with comments.

     class Solution 
        {
        public:
            void connect(TreeLinkNode *root) 
            {
                //initial 
                int maxDeep = deepCounter(root);
                if(maxDeep == 0)
                {
                    return;
                }   
                //get the counts of each layer
                int* lengthOfEachFloor = ElementCounter(maxDeep);   
                TreeLinkNode** upFloor = new TreeLinkNode*[1];
                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
                TreeLinkNode** nowFloor = new TreeLinkNode*[nowNum];    
                //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 deepCounter(TreeLinkNode *root)
            {
                int deep = 0;
                while(root != NULL)
                {
                    deep++;
                    root = root->left;
                }
                return deep;
            }
        };

  • 0
    S

    Could you please update your post? Your code seems too long.

    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.
    4. Add comments in your code.

    Thanks.


  • 0
    L

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


  • 0
    S

    @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.


  • 1
    H

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

        class Solution {
    public:
        void connect(TreeLinkNode *root) {
            
            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
            TreeLinkNode *lRoot=root->left;
            TreeLinkNode *rRoot=root->right;
            while( NULL!=lRoot->right && NULL!=rRoot->left )
            {
            	lRoot->right->next=rRoot->left;
            	lRoot=lRoot->right;
            	rRoot=rRoot->left;
            }
        }
    };

  • 0
    L

    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.


  • 0
    L

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


  • 1
    S

    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;  
        }

  • 0
    L

    @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!


  • 0
    S

    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.


  • 0
    L

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


  • 0
    Q

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


  • 0
    S

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


  • 1
    C

    Another nice method:

    void connect(TreeLinkNode *root) {
            
            if (NULL == root) {
                return;
            }
    
            TreeLinkNode *left = root->left;
            TreeLinkNode *right = root->right;
            
            /* 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);
        }

  • 0
    G

    This is a brilliant solution :)


  • 0
    R

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


  • 0
    S

    Looks pretty go, thx


Log in to reply
 

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