C++ BFS solution with 2 queues, similar to level order traversal


  • 1
    B
    void connect2(TreeLinkNode *root) {
    queue<TreeLinkNode*> q,q2;
    if(root == NULL) return;
    q.push(root);
    while(!q.empty()){
    	TreeLinkNode *tmp = q.front();
    	q.pop();
    	if(tmp->left != NULL) q2.push(tmp->left);
    	if(tmp->right != NULL) q2.push(tmp->right);
    	if(q.empty())
    		swap(q,q2);
    	else
    		tmp->next = q.front();
    }
    

    }

    q is to store nodes in current level, q2 is to store nodes in next level
    whenever an end of level is met, swap the two queue
    else, connect 'next' node.


  • 0
    K

    that's smart and neat thank you


Log in to reply
 

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