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

 题目看起来比较复杂，如果把它当做对二维数组建立链表，此时就容易想了

主要难点就是有上一层如何去控制下一层，你可以根据链表的思路，用一个dummy结点，每次指向新的一行，然后根据按照链表遍历思路，根据next结点去遍历，一边遍历一边添加下一层的结点。

class Solution {public:    void connect(TreeLinkNode *root) {        if(root == NULL) return;        root->next =NULL;        TreeLinkNode *start = root, *nextStart = new TreeLinkNode(0),*p = nextStart;        while(start){            if(start->left) {p->next = start->left;p = p->next;}            if(start->right){p->next = start->right;p = p->next;}            if(start->next ==NULL ){                p->next = NULL;                start = nextStart->next;                p = nextStart;            }else start = start->next;        }    }};