leetcode 116.填充每个节点的下一个右侧节点指针

题干

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。

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

题解

层序遍历（并没有满足常数级空间复杂度的要求）
* pre在外循环置NULL

class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> levelNode;
        if(root==NULL)
            return root;
        levelNode.push(root);
        while(!levelNode.empty()){
            int levelCount = levelNode.size();
            Node* pre = NULL;
            for(int i=0;i<levelCount;i++){
                auto now = levelNode.front();
                levelNode.pop();
                if(pre!=NULL)
                    pre->next  = now;
                pre = now;
                if(i==levelCount-1)
                    now->next = NULL;
                if(now->left!=NULL && now->right!=NULL){
                    levelNode.push(now->left);
                    levelNode.push(now->right);
                }
            }
        }
        return root;
    }
};

利用已建立的next分类讨论
* 同一父亲节点的左孩子和右孩子，可以直接建立next，对于父亲节点node，有node->left->next = node->right
* 不同父亲节点的两相邻节点（即两个子树边界处），可以通过上层（父亲节点）已经建立地next关系来建立此层的关系，对于左边节点的父亲节点node来说，有node->right->next = node->next->left
* 由于条件的完美二叉树（每个叶子结点都在同一层，每个父节点都有两个子节点），所以这么写比较方便，如果不是完美二叉树，节点的判断会变得很麻烦
如上，可写出:

class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> levelNode;
        if(root==NULL)
            return root;
        Node* leftMost = root;
        while(leftMost->left != nullptr){
            auto headNode = leftMost;
            while(headNode != nullptr){
                //第一种连接方式，共父亲节点
                headNode->left->next = headNode->right;
                //第二种连接方式，不共父亲节点
                if(headNode->next != nullptr){
                    headNode->right->next = headNode->next->left;
                }
                headNode = headNode->next;
            }
            leftMost = leftMost->left;
        }
        return root;
    }
};