LeetCode 116. 117 填充每个节点的下一个右侧节点指针 （小巧的递归、链表+二叉树）

116 填充每个节点的下一个右侧节点指针
使用额外空间很好做
递归写法

class Solution {
public:
    Node* connect(Node* root) {
        dfs(root,nullptr);
        return root;
    }
    void dfs(Node* cur,Node* nxt){
        if(!cur) return;
        cur->next = nxt;
        dfs(cur->left,cur->right);
        dfs(cur->right,cur->next?cur->next->left:nullptr);
    }
};

• 空间复杂度: O ( 1 ) O(1) O(1)

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        Node *cur = root, *header = new Node, *move;
        header->next = cur;
        while(cur){
            move = cur->left;
            while(move){
                move->next = cur->right;
                move = move->next;
                move->next = cur->next?cur->next->left:nullptr;
                move = move->next;
                cur = cur->next;
            }
            cur = header->next->left;
            header->next = cur;
        }
        delete header;
        return root;
    }
};

117 填充每个节点的下一个右侧节点指针 II
原先是通过队列来维护一整层的信息的，但是由于我们为每一层构建了一条链，
所以可以省去队列。直接使用next指针去遍历这条链。

• 具体的来说
  找到每一层的链的起点，然后记录用next指针连接两个不为空的节点。

class Solution {
public:
    void handle(Node* &last,Node *p,Node* &nextStart){
        if(last){
            last->next = p;
        }
        // 找到下个起点就不再更新了
        if(nextStart == nullptr){
            nextStart = p;
        }
        last = p;
    }

    Node* connect(Node* root) {
        Node* start = root;
        while(start){
            Node *last = nullptr,*nextStart = nullptr;
            // 用第 i 层的链, 为 i+1 层 构建 next 指针 
            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;
    }
};