LeetCode#117

LeetCode#117填充每个节点的下一个右侧节点指针 II

题目链接
一开始让我想简单了，忽略了next节点可能是另一棵树上的可能性了人傻了，其实我们就可以简单理解为一个广度优先搜索，分别遍历每一层，在同一层时，当前节点的是上一个节点的next节点（第一个节点除外），我们可以每次把第一个节点作为空指针，让最后一个节点指向它。
附代码：

/*
// 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 == nullptr)
            return nullptr;
        root -> next = nullptr;
        queue<Node*>qu;
        qu.push(root);
        while(!qu.empty())
        {
            int length = qu.size();
            Node* old = nullptr;
            for(int i = 0; i< length ; i++)
            {
                Node* temp = qu.front();
                qu.pop();
                if(temp -> left != nullptr)
                    qu.push(temp ->left);
                if(temp -> right != nullptr)
                    qu.push(temp -> right);
                if(i != 0)
                    old -> next = temp;
                old = temp;

            }
        }
       return root; 
    }
};