leetcode:237 填充每个节点的下一个右侧节点指针

题目如下：

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
 int val;
 Node *left;
 Node *right;
 Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。
进阶：

• 你只能使用常量级额外空间。
• 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一开始使用deque写的,代码如下：

    Node *connect(Node *root)
    {
        if (nullptr == root || nullptr == root->left) //return if there is only 0 or none node
            return root;
        deque<decltype(root)> deq; //deq to perform depth first serch
        deq.push_back(root); //insert first node 
        while (!deq.empty())
        {
            int cnt = deq.size() - 1; //fetch number of node for each layer
            auto node = deq.front();
            //handle first node in a specific layer
            if (nullptr != node->left)
            {
                deq.push_back(node->left); 
                deq.push_back(node->right);
            }
            deq.pop_front();
            //handle the rest of the node in the specific layer
            for (; cnt > 0; cnt--)
            {
                node->next = deq.front();
                node = deq.front();
                deq.pop_front();
                if (nullptr != node->left)
                {
                    deq.push_back(node->left);
                    deq.push_back(node->right);
                }
            }
        }
        return root;
    }

过是过了，但是这样做出来不符合进阶要求，后面就偷偷看了下讨论区，好吧我这波是直接把next指针忘了。。。
新写的解法如下：

    Node *connect(Node *root)
    {
        if (nullptr == root || nullptr == root->left)
            return root;
        auto node = root;
        while (nullptr != node->left)
        {
            auto ptr = node;
            while (nullptr != ptr)
            {
                ptr->left->next = ptr->right;
                if (nullptr != ptr->next)
                    ptr->right->next = ptr->next->left;
                ptr = ptr->next;
            }
            node = node->left;
        }
        return root;
    }