[Leetcode] Populating Next Right Pointers in Each Node

Given a binary tree

    struct TreeLinkNode {

      TreeLinkNode *left;

      TreeLinkNode *right;

      TreeLinkNode *next;

    }

 
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to  NULL .
Initially, all next pointers are set to  NULL .
Note:

You may only use constant extra space.

You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

 
For example,Given the following perfect binary tree,

         1

       /  \

      2    3

     / \  / \

    4  5  6  7

 
After calling your function, the tree should look like:

         1 -> NULL

       /  \

      2 -> 3 -> NULL

     / \  / \

    4->5->6->7 -> NULL

층층이 두루 다니다

 1 /**

 2  * Definition for binary tree with next pointer.

 3  * struct TreeLinkNode {

 4  *  int val;

 5  *  TreeLinkNode *left, *right, *next;

 6  *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}

 7  * };

 8  */

 9 class Solution {

10 public:

11     void connect(TreeLinkNode *root) {

12        if (root == NULL) {

13             return;

14         }

15         queue<TreeLinkNode* > q;

16         TreeLinkNode *p;

17         int idx = 1, n;

18         q.push(root);

19         while (!q.empty()) {

20             n = idx - 1;

21             idx = 0;

22             p = q.front();

23             if (q.front()->left != NULL) {

24                 q.push(q.front()->left);

25                 idx++;

26             }

27             if (q.front()->right != NULL) {

28                 q.push(q.front()->right);

29                 idx++;

30             }

31             q.pop();

32             for (int i = 0; i < n; ++i) {

33                 p->next = q.front();

34                 if (q.front()->left != NULL) {

35                     q.push(q.front()->left);

36                     idx++;

37                 }

38                 if (q.front()->right != NULL) {

39                     q.push(q.front()->right);

40                     idx++;

41                 }

42                 p = p->next;

43                 q.pop();

44             }

45             p->next = NULL;

46         } 

47     }

48 };