leetcode日记（100）填充每个节点的下一个右侧节点指针

和层序遍历差不多的思路，将节点储存在队列里，一边取出节点一边放入取出节点的左右节点，直到队列空。

/*
// 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) {
        if(root==NULL) return root;
        int record=1;
        queue<Node*> n;
        n.push(root);
        while(!n.empty()){
            Node* node=NULL;
            for(int i=0;i<record;i++){
                Node* first=n.front();
                if(first->left){
                    n.push(first->left);
                    n.push(first->right);
                }
                if(node) node->next=first;
                node=first;
                n.pop();
            }
            record*=2;
        }
        return root;
    }
};

本来我是写的vector，但是发现queue更好，完美匹配。

以及看了答案发现还有一种很机智的思路。

大概就是next有两种取法（对于root和其left、right），一种是left的next为right，一种是right的next为root的next的left。

如此就可以递归。

/*
// 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* result=root;
        while(root){
            Node* record=root->left;
            while(root&&root->left){
                root->left->next=root->right;
                if(root->next) root->right->next=root->next->left;
                root=root->next;
            }
            root=record;
        }
        return result;
    }
};