/**
* 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
*
* 跟进“在每个节点中填充下一个右指针”的问题。
* 如果给定的树可以是任何二叉树呢？您以前的解决方案是否仍然有效？
* 音符：
* 您只能使用恒定的额外空间。
* 例如，
* 给定以下二叉树，
* 1
* /
* 2 3
* /
* 4 5 7
* 调用函数后，树应如下所示：
* 1 -> NULL
* /
* 2 -> 3 -> NULL
* /
* 4-> 5 -> 7 -> NULL
*/
/**
* 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
*
* 跟进“在每个节点中填充下一个右指针”的问题。
* 如果给定的树可以是任何二叉树呢？您以前的解决方案是否仍然有效？
* 音符：
* 您只能使用恒定的额外空间。
* 例如，
* 给定以下二叉树，
* 1
* /
* 2 3
* /
* 4 5 7
* 调用函数后，树应如下所示：
* 1 -> NULL
* /
* 2 -> 3 -> NULL
* /
* 4-> 5 -> 7 -> NULL
*/
public class Main45 {
public static void main(String[] args) {
}
public class TreeLinkNode {
int val;
TreeLinkNode left, right, next;
TreeLinkNode(int x) { val = x; }
}
public void connect(TreeLinkNode root) {
if (root == null) {
return ;
}
LinkedList<TreeLinkNode> link = new LinkedList<>();
link.offer(root);
while (!link.isEmpty()) {
TreeLinkNode head = link.peek();
link.poll();
int size = link.size();
if (head.left != null) {
link.offer(head.left);
}
if (head.right != null) {
link.offer(head.right);
}
while (size > 0) {
TreeLinkNode tree = link.peek();
link.poll();
head.next = tree;
head = tree;
if (tree.left != null) {
link.offer(tree.left);
}
if (tree.right != null) {
link.offer(tree.right);
}
size--;
}
head.next = null;
}
}
}