Simple abstract BF C++ Solution


  • 0
    S

    I noticed that this question is asking for a very simple thing, which is all the nodes in a given level should point to each other as a list. This is a clear BF problem. In this solution i abstracted everything out by using the null value, will explain more. You don't need to worry about knowing which level this node belongs to or where/how it belongs in the Tree structure.

    Initially, after validations, i push the root to the queue then a NULL. This NULL is used as a level end indicator. Inside the loop, i take the first element in the queue and make it point to the next one:

    • nodes.pop already makes the next at the front
    • if next is NULL, that's ok as the last node in the level points to NULL as next.

    Then i keep adding children nodes, ignoring null ones so it won't confuse with my NULL level terminator.

    When NULL is at the top of the queue, it means a level has been already processed. If there's still nodes in the next level, they're all already in the queue, so i push the NULL back in which marks the end of the next level. Otherwise the queue can be empty, in this case will do nothing and loop terminates.

    void connect(TreeLinkNode *root) {
            if(!root || (!root->left && !root->right) )
                return;
            
            queue<TreeLinkNode*> nodes;
    		nodes.push(root);
    		nodes.push(NULL);
    		
    		while (!nodes.empty())
    		{
    			TreeLinkNode * node = nodes.front();
    			nodes.pop();
    			if(node)
    			{
    				node->next = nodes.front();
    				if(node->left)
    					nodes.push(node->left);
    				if(node->right)
    					nodes.push(node->right);
    			}
    			else if(!nodes.empty())
    				nodes.push(NULL);
    		}
        }

  • 0
    S

    it is not an O(1) solution, you can improve it.


Log in to reply
 

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