LeetCode Populating Next Right Pointers in Each Node II

class Solution {
public:
    void connect(TreeLinkNode *root) {
        if (root == NULL) return;
        queue<TreeLinkNode*> que;
        que.push(root);
        int level_count = 1;
        while (level_count > 0) {
            while (level_count--) {
                TreeLinkNode* cur = que.front();
                que.pop();
                if (level_count == 0) {
                    cur->next = NULL;
                } else {
                    cur->next = que.front();
                }
                if (cur->left != NULL) {
                    que.push(cur->left);
                }
                if (cur->right != NULL) {
                    que.push(cur->right);
                }
            }
            level_count = que.size();
        }
    }
};

按层遍历，用到了队列，不过题目要求使用常量空间该如何是好呢？

看了下讨论，因为提供了next指针，其实在原来的树结构上按照题目意思设定next指针后，每一层就可以按序遍历了，其实提供了一个天然的代替前面方法中的queue的形式，空间也不随问题规模增长。

对cnblogs的编辑器很失望为什么就不能正确显示了

void connect(TreeLinkNode *root) {
    TreeLinkNode* next_level_head = root;
    TreeLinkNode* level_cur;
    TreeLinkNode* next_level_pre;
    TreeLinkNode* next_level_cur;
    
    int stage = 0;
    
    while (next_level_head != NULL) {
        level_cur = next_level_head;
        next_level_head = NULL;
        next_level_pre  = NULL;
        next_level_cur  = NULL;
        stage = 0;
        while (level_cur != NULL) {
            if (stage == 2) {
                level_cur = level_cur->next;
                stage = 0;
                continue;
            }
            if (stage == 1) {
                stage++;
                next_level_cur = level_cur->right;
            }
            if (stage == 0) {
                stage++;
                next_level_cur = level_cur->left;
            }
            if (next_level_cur == NULL) continue;
            
            if (next_level_head == NULL) {
                next_level_head = next_level_cur;
            }
            if (next_level_pre != NULL) {
                next_level_pre->next = next_level_cur;
            }
            next_level_pre = next_level_cur;
        }
    }
}

第二轮：
Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

You may only use constant extra space.
For example,
Given the following binary tree,

         1
       /  
      2    3
     /     
    4   5    7
After calling your function, the tree should look like:
         1 -> NULL
       /  
      2 -> 3 -> NULL
     /     
    4-> 5 -> 7 -> NULL

毫无长进啊，依然没有想到

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        TreeLinkNode* que = root;
        TreeLinkNode* cur = NULL;
        while (que != NULL) {
            cur = que;
            TreeLinkNode dummyHead(0);
            TreeLinkNode* tail = &dummyHead;
            while (cur != NULL) {
                if (cur->left != NULL) {
                    tail->next = cur->left;
                    tail = tail->next;
                }
                if (cur->right != NULL) {
                    tail->next = cur->right;
                    tail = tail->next;
                }
                cur = cur->next;
            }
            que = dummyHead.next;
        }
    }
};

好了我已经记住了overfitting了

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        TreeLinkNode dummy(0);
        TreeLinkNode* iter = root;
        TreeLinkNode* tail = NULL;
        while (iter != NULL) {
            tail = &dummy;
            while (iter != NULL) {
                if (iter->left != NULL) {
                    tail->next = iter->left;
                    tail = iter->left;
                }
                if (iter->right != NULL) {
                    tail->next = iter->right;
                    tail = iter->right;
                }
                iter = iter->next;
            }
            iter = dummy.next;
            dummy.next = NULL;
        }
    }
};