/*

Author: King, wangjingui@gmail.com

Date: Oct 7, 2014

Problem: Populating Next Right Pointers in Each Node II

Difficulty: Easy

Source: https://oj.leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/

Notes:

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

Solution: 1. iterative way with CONSTANT extra space.

2. iterative way + queue. Contributed by SUN Mian(孙冕).

3. recursive solution.

*/

/**

* Definition for binary tree with next pointer.

* public class TreeLinkNode {

* int val;

* TreeLinkNode left, right, next;

* TreeLinkNode(int x) { val = x; }

* }

*/

public class Solution {

public void connect(TreeLinkNode root) {

if (root == null) return;

TreeLinkNode dummy = new TreeLinkNode(-1);

TreeLinkNode pre = dummy;

TreeLinkNode cur = root;

while (cur != null) {

if (cur.left != null) {

pre.next = cur.left;

pre = pre.next;

}

if (cur.right != null) {

pre.next = cur.right;

pre = pre.next;

}

cur = cur.next;

}

connect(dummy.next);

}

}