A solution, by using a BFS tree


  • 1
    H
    void connect(TreeLinkNode *root)
    {
    	if (!root)return;
    	deque<TreeLinkNode*> Q;
    	Q.push_back(root);
    
    	// node number of the same distance from the root in the BFS tree
    	int nodeNumber = Q.size();
    	while (!Q.empty())
    	{
    		TreeLinkNode* nodePtr = Q.front(); Q.pop_front();
    		nodeNumber--;
    
    		if (nodePtr->left)
    			Q.push_back(nodePtr->left);
    		if (nodePtr->right)
    			Q.push_back(nodePtr->right);
    
    		if (nodeNumber == 0)
    		{
    			nodePtr->next = nullptr;
    			nodeNumber = Q.size();
    		}
    		else // nodeNumber != 0
    			nodePtr->next = Q.front();
    	}
    }

Log in to reply
 

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