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

分析

要使空间复杂度为常数，那么就不能使用bfs，用last表示当前root的左子树，将左子树的Next赋成root->right即可，然后每一次从每一层的第一个节点开始遍历。

class Solution {
public:
    void handle(Node* &last,Node* &p,Node* &nextStart){
        if(last){
            last->next=p;
        }
        if(!nextStart){
            nextStart=p;
        }
        last=p;
    }
    Node* connect(Node* root) {
        if(!root)return root;
        Node* start=root;
        while(start){
            Node* last=nullptr,*nextStart=nullptr;
            for(Node*p=start;p!=nullptr;p=p->next){
                if(p->left){
                    handle(last,p->left,nextStart);
                }
                if(p->right){
                    handle(last,p->right,nextStart);
                }
            }
            start=nextStart;
        }
        return root;
    }
};