[LeetCode] Populating Next Right Pointers in Each Node II_综合

[Problem]

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

[Analysis]
层次遍历，用两个队列，Q1存储TreeLinkNode，另一个Q2存储Q1中每个结点所在的level，将同一level的TreeLinkNode连成一条线。

[Solution]

//
// 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) {
      
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
       
        // null root
        if(NULL == root){
      
            return;
        }
   
        // push root node
        queue<TreeLinkNode *> nodeQueue;
        queue<int> levelQueue;
        if(root->left != NULL){
      
            nodeQueue.push(root->left);
            levelQueue.push(1);
        }
        if(root->right != NULL){
      
            nodeQueue.push(root->right);
            levelQueue.push(1);
        }
   
        // lever order traversal
        TreeLinkNode *pre = root;
        TreeLinkNode *cur = root;
        int preLevel = 0, curLevel = 0;
        while(!nodeQueue.empty()){
      
            cur = nodeQueue.front();
            curLevel = levelQueue.front();
   
            // push children
            if(cur->left != NULL){
      
                nodeQueue.push(cur->left);
                levelQueue.push(curLevel + 1);
            }
            if(cur->right != NULL){
      
                nodeQueue.push(cur->right);
                levelQueue.push(curLevel + 1);
            }
   
            // set next
            if(preLevel == curLevel){
      
                pre->next = cur;
            }
            pre = cur;
            preLevel = curLevel;
   
            // pop
            nodeQueue.pop();
            levelQueue.pop();
        }
    }
};