Populating Next Right Pointers in Each Node I&II

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */

/*
BFS
*/
class Solution {
public:
    void connect(TreeLinkNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (root == NULL) return;
        
        deque<TreeLinkNode*> que;
        que.push_back(root);
        que.push_back(NULL); //layer delimiter
        
        while (! que.empty())
        {
            TreeLinkNode *cur = que.front(); que.pop_front();
            
            if (cur == NULL)
            {
                /*
                I keep receiving segmentation fault with this code. 
                Find out why!!!!
                given input {0}
                */
                for (int i = 0; i < que.size() - 1; ++i)
                {
                   que[i]->next = que[i + 1];
                }
                if (not que.empty()) que.push_back(NULL);
            }
            else
            {
                if (cur->left != NULL)  que.push_back(cur->left);
                if (cur->right != NULL) que.push_back(cur->right);
            }
        }
    }
};
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s