Given a binary tree
struct TreeLinkNode {
TreeLinkNode *left;
TreeLinkNode *right;
TreeLinkNode *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
Note:
You may only use constant extra space.
You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
For example,
Given the following perfect binary tree,
1
/
2 3
/ \ /
4 5 6 7
After calling your function, the tree should look like:
1 -> NULL
/
2 -> 3 -> NULL
/ \ /
4->5->6->7-> NULL
题意：有这样一个二叉树，节点中有一个next指针，要求把每个节点的next指针指向和它同层的右边的节点，如果右边没有节点，将next指向null。
思路：
之前做过一道按层遍历二叉树的题目，可以在此基础上解决这道题。
在遍历每层节点的时候，可以用两个指针pre和cur，一个指向前一个节点，一个指向当前节点。
每次循环将pre的next指向cur，然后再把pre更新为cur，因为在下一次循环中当前的cur就是pre了。
public void connect(TreeLinkNode root) {
if (root == null) {
return;
}
Queue<TreeLinkNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
TreeLinkNode pre = null;
for (int i = 0; i < size; i++) {
if (pre == null) {
pre = q.poll();
} else {
TreeLinkNode cur = q.poll();
pre.next = cur;
pre = cur;
}
if (pre.left != null) {
q.offer(pre.left);
}
if (pre.right != null) {
q.offer(pre.right);
}
}
pre.next = null;
}
}