Simple C++ solution using a queue


  • 0
    M

    The idea is simple. Use a queue to store the nodes level by level, and count the total number of nodes at each level. While popping elements from the queue, if not the last element at the level, let the next of it be the front of the queue; otherwise, let the next of it be NULL.

    class Solution {
    public:
        void connect(TreeLinkNode *root) {
            if(!root) return;
            queue<TreeLinkNode*> nodes;
            nodes.push(root);
            int left = 1;
            int level =0;
            while(!nodes.empty()){
                TreeLinkNode *temp;
                temp = nodes.front();
                nodes.pop();
                
                if(temp->left){
                    nodes.push(temp->left);
                    level++;
                }
                if(temp->right){
                    nodes.push(temp->right);
                    level++;
                }
                if(left == 1){
                    temp->next = NULL;
                    left--;
                }
                else{
                    temp->next = nodes.front();
                    left--;
                }
                if(left==0){
                    left = level;
                    level =0;
                }
                
            }
        }
    };

Log in to reply
 

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