Description

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

Explain

这道题的意思就是让树的每一层的每个节点连接成一个链表。而且空间复杂度是O(1)，好用的队列的层序遍历一下子就被限制了。幸好这道题给我们的树是完美二叉树。我们只要在上一层时将下一层的节点连接好就行了，因为上一层已经是被连接好的了，是有序的，遍历上一层，将下一层的节点连接起来就好了。只是在遍历每一层时将下一层的头结点保存下来，如果头结点为空，那么我们的算法就完结了。

Code

class Solution {
public:
    void connect(TreeLinkNode *root) {
        if (!root) return;
        TreeLinkNode* start = root, *temp;
        while(start) {
            temp = start;
            start = start->left;
            while(temp) {
                if (temp->left && temp->right) {
                    temp->left->next = temp->right;
                    if (temp->next) {
                        temp->right->next = temp->next->left;
                    }
                }
                temp = temp->next;
            }
        }
    }
};