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
You may only use constant extra space.
* 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) {
TreeLinkNode first = root; //每层第一个
while (first != null) {
TreeLinkNode cur = first;
TreeLinkNode prev = null;
while (cur != null) {
if (cur.left != null) {
if (prev != null) {
prev.next = cur.left;
} else {
first = cur.left;
}
prev = cur.left;
}
if (cur.right != null) {
if (prev != null) {
prev.next = cur.right;
} else {
first = cur.right;
}
prev = cur.right;
}
cur = cur.next;
}
//当没有孩子时, break
if (cur == null && prev == null) {
break;
}
}
}
}
若没有空间限制,level order traversal