学步园

题意：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.

思路：看到这道题，很容易想到利用层序遍历的思想，得到每层节点的所有左右子节点，然后指向。

class Solution {
public:
    void connect(TreeLinkNode *root) {
        /*****************************************
         * 队列的长度最好取10000以上，前面WA是因为队列的长度太小了
         * ****************************************/
        TreeLinkNode* Q[10000];
        int front = 0, rear = -1;
        int i;
        Q[++rear] = root;  
        if (Q[rear] == NULL)
        {
            return;
        }
        int index;
        while(front <= rear)
        {
            index = rear;
            for(i = front; i <= index; i++)
            {
                if (Q[i]->left != NULL)
                {
                    Q[++rear] = Q[i]->left;
                    Q[rear]->next = Q[i]->right;
                }
                if (Q[i]->right != NULL)
                {
                    Q[++rear] = Q[i]->right;
                    Q[rear]->next = (i+1<=index) ? Q[i+1]->left : NULL;
                }
            }
            front = index + 1;
        }
    }
};