My clear c++ solution with clear explanation


  • 0
    H

    //in fact,my solution is based on the level-order which uses a queue to complish it. The node last, and nlast point to the last element in current level line, and nlast point the next-level line. In the process, we use a vector to storage every level elements and after getting that, the remaining process is easy to understand.

    class Solution {

    public:

    void connect(TreeLinkNode *root) {
        if(root==NULL) return;
        TreeLinkNode* last=root;
        TreeLinkNode* nlast=NULL;
        queue<TreeLinkNode*> que;
        vector< vector<TreeLinkNode*> > vec;
        vector<TreeLinkNode*> vectemp;
        que.push(root);
        while(!que.empty()){
            TreeLinkNode* temp=que.front();
            que.pop();
            if(temp->left){
                que.push(temp->left);
                nlast=temp->left;
            }
            if(temp->right){
                que.push(temp->right);
                nlast=temp->right;
            }
            if(temp==last){
                last=nlast;
                vectemp.push_back(temp);
                vec.push_back(vectemp);
                vectemp.clear();
            }
            else{
                vectemp.push_back(temp);
            }
        }
        for(int i=0;i<vec.size();i++){
            for(int j=0;j<vec[i].size();j++){
                if(j==vec[i].size()-1){
                    vec[i][j]->next=NULL;
                }
                else{
                    vec[i][j]->next=vec[i][j+1];
                }
            }
        }
    }
    

    };


Log in to reply
 

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