Populating Next Right Pointers in Each Node2

题目地址：https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/#/description

题目：

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

解题思路：
这道题只需要维持三个变量：head，curr和prev。每次通过判断prev是否为null来看是否需要进入下一层。如果需要进入下一层，那么就需要将prev从head的next开始。


代码：

class TreeLinkNode{
    TreeLinkNode left;
    TreeLinkNode right;
    TreeLinkNode next;
    int val;
    public TreeLinkNode(int val){
        this.val = val;
    }
}
public void connect(TreeLinkNode root) {
    TreeLinkNode head = new TreeLinkNode(0);
    TreeLinkNode curr = head;
    TreeLinkNode prev = root;
    while(prev != null){
        if(prev.left != null){
            curr.next = prev.left;
            curr = curr.next;
        }
        if(prev.right != null){
            curr.next = prev.right;
            curr = curr.next;
        }
        prev = prev.next;
        if(prev == null){
            prev = head.next;
            head.next = null;
            curr = head;
        }
    }
}