leetcode116. 填充每个节点的下一个右侧节点指针

分析

层序遍历将每层的节点存下来然后再将每层的指针指向下一个。

class Solution {
public:
    Node* connect(Node* root) {
        if(!root)return root;
        queue<Node*>q;
        q.push(root);
        while(q.size()){
            int n=q.size();
            vector<Node*> lever;
            for(int i=0;i<n;i++){
                auto t=q.front();
                q.pop();
                lever.push_back(t);
                if(t->left)q.push(t->left);
                if(t->right)q.push(t->right);
            }
            for(int i=0;i<n-1;i++){
                lever[i]->next=lever[i+1];
            }
            lever[n-1]->next=NULL;
        }
        return root;
    }
};