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
題意：有這樣一個(gè)二叉樹(shù)芦疏，節(jié)點(diǎn)中有一個(gè)next指針宴倍，要求把每個(gè)節(jié)點(diǎn)的next指針指向和它同層的右邊的節(jié)點(diǎn)，如果右邊沒(méi)有節(jié)點(diǎn)，將next指向null凳干。
思路：
之前做過(guò)一道按層遍歷二叉樹(shù)的題目泉瞻，可以在此基礎(chǔ)上解決這道題谴分。
在遍歷每層節(jié)點(diǎn)的時(shí)候鸠天，可以用兩個(gè)指針pre和cur，一個(gè)指向前一個(gè)節(jié)點(diǎn)手形，一個(gè)指向當(dāng)前節(jié)點(diǎn)啥供。
每次循環(huán)將pre的next指向cur，然后再把pre更新為cur库糠，因?yàn)樵谙乱淮窝h(huán)中當(dāng)前的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;
}
}