https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/ DFS,BFS

117. Populating Next Right Pointers in Each Node II.cpp

/**
 我的方法用了一个queue,再用一个NULL指针来分辨是不是一层的。
 看了答案以后发现optimized的解法是，不需要用queue，因为这个next的link已经可以serve as queue.
 
 * 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) {
        queue<TreeLinkNode*> q;
        q.push(root);
        q.push(NULL);
        while (q.front()){
            while(q.front()){
                TreeLinkNode* cur = q.front();
                q.pop();
                cur->next = q.front();
                if (cur->left) q.push(cur->left);
                if (cur->right) q.push(cur->right);
            }
            q.pop();
            q.push(NULL);
        }
    }
};

我得只用这个linked list再做一遍。思路就是linked list可以serve as queue.