題目描述（中等難度）
給定一個二叉樹，然后每個節(jié)點有一個 next 指針，將它指向它右邊的節(jié)點。和 116 題 基本一樣扣孟，區(qū)別在于之前是滿二叉樹。
解法一 BFS
直接把 116 題 題的代碼復(fù)制過來就好荣赶，一句也不用改凤价。
利用一個棧將下一層的節(jié)點保存。通過pre指針把棧里的元素一個一個接起來拔创。
public Node connect(Node root) {
if (root == null) {
return root;
}
Queue<Node> queue = new LinkedList<Node>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
Node pre = null;
for (int i = 0; i < size; i++) {
Node cur = queue.poll();
if (i > 0) {
pre.next = cur;
}
pre = cur;
if (cur.left != null) {
queue.offer(cur.left);
}
if (cur.right != null) {
queue.offer(cur.right);
}
}
}
return root;
}
解法二
當然題目要求了空間復(fù)雜度利诺，可以先到 116 題 看一下思路，這里在上邊的基礎(chǔ)上改一下剩燥。
我們用第二種簡潔的代碼慢逾，相對會好改一些。
Node connect(Node root) {
if (root == null)
return root;
Node pre = root;
Node cur = null;
while (pre.left != null) {
cur = pre;
while (cur != null) {
cur.left.next = cur.right;
if (cur.next != null) {
cur.right.next = cur.next.left;
}
cur = cur.next;
}
pre = pre.left;
}
return root;
}
需要解決的問題還是挺多的灭红。
cur.left.next = cur.right;
cur.right.next = cur.next.left;
之前的關(guān)鍵代碼就是上邊兩句侣滩，但是在這道題中我們無法保證cur.left 或者 cur.right 或者 cur.next.left或者cur.next.right 是否為null逸贾。所以我們需要用一個while循環(huán)來保證當前節(jié)點至少有一個孩子漱竖。
while (cur.left == null && cur.right == null) {
cur = cur.next;
}
這樣的話保證了當前節(jié)點至少有一個孩子，然后如果一個孩子為 null综膀，那么就可以保證另一個一定不為 null 了赁项。
整體的話葛躏，就用了上邊介紹的技巧澈段，代碼比較長悠菜，可以結(jié)合的看一下。
Node connect(Node root) {
if (root == null)
return root;
Node pre = root;
Node cur = null;
while (true) {
cur = pre;
while (cur != null) {
//找到至少有一個孩子的節(jié)點
if (cur.left == null && cur.right == null) {
cur = cur.next;
continue;
}
//找到當前節(jié)點的下一個至少有一個孩子的節(jié)點
Node next = cur.next;
while (next != null && next.left == null && next.right == null) {
next = next.next;
if (next == null) {
break;
}
}
//當前節(jié)點的左右孩子都不為空败富，就將 left.next 指向 right
if (cur.left != null && cur.right != null) {
cur.left.next = cur.right;
}
//要接上 next 的節(jié)點的孩子悔醋，所以用 temp 處理當前節(jié)點 right 為 null 的情況
Node temp = cur.right == null ? cur.left : cur.right;
if (next != null) {
//next 左孩子不為 null，就接上左孩子兽叮。
if (next.left != null) {
temp.next = next.left;
//next 左孩子為 null芬骄，就接上右孩子猾愿。
} else {
temp.next = next.right;
}
}
cur = cur.next;
}
//找到擁有孩子的節(jié)點
while (pre.left == null && pre.right == null) {
pre = pre.next;
//都沒有孩子說明已經(jīng)是最后一層了
if (pre == null) {
return root;
}
}
//進入下一層
pre = pre.left != null ? pre.left : pre.right;
}
}
解法三
參考 這里。
利用解法一的思想账阻，我們利用 pre 指針蒂秘，然后一個一個取節(jié)點，把它連起來淘太。解法一為什么沒有像解法二那樣考慮當前節(jié)點為 null 呢姻僧？因為我們沒有添加為 null 的節(jié)點，就是下邊的代碼的作用蒲牧。
if (cur.left != null) {
queue.offer(cur.left);
}
if (cur.right != null) {
queue.offer(cur.right);
}
所以這里是一樣的撇贺，如果當前節(jié)點為null不處理就可以了。
第二個問題冰抢，怎么得到每次的開頭的節(jié)點呢松嘶？我們用一個dummy指針，當連接第一個節(jié)點的時候挎扰，就將dummy指針指向他翠订。此外，之前用的pre指針遵倦，把它當成tail指針可能會更好理解蕴轨。如下圖所示：
cur 指針利用 next 不停的遍歷當前層。
如果 cur 的孩子不為 null 就將它接到 tail 后邊骇吭，然后更新tail橙弱。
當 cur 為 null 的時候，再利用 dummy 指針得到新的一層的開始節(jié)點燥狰。
dummy 指針在鏈表中經(jīng)常用到棘脐，他只是為了處理頭結(jié)點的情況，它并不屬于當前鏈表龙致。
代碼就異常的簡單了蛀缝。
Node connect(Node root) {
Node cur = root;
while (cur != null) {
Node dummy = new Node();
Node tail = dummy;
//遍歷 cur 的當前層
while (cur != null) {
if (cur.left != null) {
tail.next = cur.left;
tail = tail.next;
}
if (cur.right != null) {
tail.next = cur.right;
tail = tail.next;
}
cur = cur.next;
}
//更新 cur 到下一層
cur = dummy.next;
}
return root;
}
總
本來為了圖方便，在 116 題 的基礎(chǔ)上把解法二改了出來目代，還搞了蠻久屈梁，因為為 null 的情況太多了，不停的報空指針異常榛了，最后終于理清了思路在讶。但和解法三比起來實在是相形見絀了，解法三太優(yōu)雅了霜大，但其實這才是正常的思路构哺，從解法一的做法產(chǎn)生靈感，利用 tail 指針將它們連起來。
更多詳細通俗題解詳見 leetcode.wang 曙强。
