題目地址
https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii/
題目描述
給定一個(gè)二叉樹
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每個(gè) next 指針，讓這個(gè)指針指向其下一個(gè)右側(cè)節(jié)點(diǎn)。如果找不到下一個(gè)右側(cè)節(jié)點(diǎn)，則將 next 指針設(shè)置為 NULL谤狡。
初始狀態(tài)下斯稳，所有 next 指針都被設(shè)置為 NULL吞鸭。
進(jìn)階：
你只能使用常量級額外空間灼擂。
使用遞歸解題也符合要求围详，本題中遞歸程序占用的椓蛱担空間不算做額外的空間復(fù)雜度衩婚。
示例：
輸入：root = [1,2,3,4,5,null,7]
輸出：[1,#,2,3,#,4,5,7,#]
解釋：給定二叉樹如圖 A 所示，你的函數(shù)應(yīng)該填充它的每個(gè) next 指針碍论，以指向其下一個(gè)右側(cè)節(jié)點(diǎn)谅猾，如圖 B 所示柄慰。
提示：
樹中的節(jié)點(diǎn)數(shù)小于 6000
-100 <= node.val <= 100
思路
- 借助棧層次遍歷來連接next, 每一層遍歷完都有個(gè)子循環(huán)遍歷下一層(同時(shí)連接next), root遍歷完, 遍歷下一層, root.left和root.right, 同時(shí)連接next, 這時(shí)下一層也都添加進(jìn)queue, 接著遍歷下一層.
- 遞歸連接, 先將右邊子樹連接好, 否則某一層的子樹中間間隔很多空的就是就會(huì)誤認(rèn)為中間的子樹是最右側(cè)子樹. 因?yàn)樯弦粚雍陀疫呑訕涠际沁B接好的, 所以next都可以直接通過root.next.next.....找到.
題解
/**
* Created by zcdeng on 2021/2/22.
*/
public class TreeConnectV2 {
public static void main(String[] args) {
Node root = Node.create(new int[] {1, 2, 3, 4, 5, -1, 7});
Node ret = connect(root);
root = Node.create(new int[] {1, 2, 3, 4, 5});
ret = connectV0(root);
}
/**
* 執(zhí)行用時(shí)：3 ms, 在所有 Java 提交中擊敗了8.80%的用戶
* 內(nèi)存消耗：38.3 MB, 在所有 Java 提交中擊敗了12.48%的用戶
*/
private static Node connectV0(Node root) {
if (root == null) {
return null;
}
List<Node> queue = new ArrayList<Node>();
queue.add(root);
while (queue.size() > 0) {
int size = queue.size();
while (size > 0) {
size--;
Node node = queue.remove(0);
if (size > 0 && queue.size() > 0) {
node.next = queue.get(0);
}
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}
return root;
}
/**
* 執(zhí)行用時(shí)：0 ms, 在所有 Java 提交中擊敗了100.00%的用戶
* 內(nèi)存消耗：38.4 MB, 在所有 Java 提交中擊敗了7.56%的用戶
*/
private static Node connect(Node root) {
if (root == null) {
return root;
}
if (root.left != null) {
if (root.right != null) {
root.left.next = root.right;
} else {
root.left.next = getNext(root.next);
}
}
if (root.right != null) {
root.right.next = getNext(root.next);
}
connect(root.left);
connect(root.right);
return root;
}
private static Node getNext(Node next) {
while (next != null) {
if (next.left != null) {
return next.left;
}
if (next.right != null) {
return next.right;
}
next = next.next;
}
return null;
}
}
