117. 填充每個節(jié)點的下一個右側節(jié)點指針 II

難度：中等

題目

給定一個二叉樹：

struct Node {int val;Node *left;Node *right;Node *next;
}

填充它的每個 next 指針，讓這個指針指向其下一個右側節(jié)點。如果找不到下一個右側節(jié)點，則將 next 指針設置為 NULL 。

初始狀態(tài)下，所有 next 指針都被設置為 NULL 。

示例 1：

輸入：root = [1,2,3,4,5,null,7]
輸出：[1,#,2,3,#,4,5,7,#]
解釋：給定二叉樹如圖 A 所示，你的函數(shù)應該填充它的每個 next 指針，以指向其下一個右側節(jié)點，如圖 B 所示。序列化輸出按層序遍歷順序（由 next 指針連接），'#' 表示每層的末尾。

示例 2：

輸入：root = []
輸出：[]

提示：

• 樹中的節(jié)點數(shù)在范圍 [0, 6000] 內(nèi)
• -100 <= Node.val <= 100

進階：

• 你只能使用常量級額外空間。
• 使用遞歸解題也符合要求，本題中遞歸程序的隱式棧空間不計入額外空間復雜度

個人題解

思路：

1. 考慮逐層遍歷，考慮用一個list來充當層的概念，每次遍歷當前層的時候，把下一層的節(jié)點先裝到list中
2. 則當list中沒有節(jié)點時，表示所有節(jié)點遍歷完畢；有節(jié)點則繼續(xù)遍歷，遍歷時用一個指針完成next的賦值，將當前層節(jié)點串起來

class Solution {
public Node connect(Node root) {if (root == null) {return null;}ArrayList<Node> list = new ArrayList<>();list.add(root);while (!list.isEmpty()) {ArrayList<Node> nextList = new ArrayList<>(); // 記錄下一層遍歷的節(jié)點Node curNode = null; // 用于連接for (Node node : list) {if (node.left != null) {nextList.add(node.left);if (curNode != null) {curNode.next = node.left;}curNode = node.left;}if (node.right != null) {nextList.add(node.right);if (curNode != null) {curNode.next = node.right;}curNode = node.right;}}list = nextList;}return root;}
}

進階：

1. 上面層的概念是用list來表示的，分析一下，
   • 如果用一個指針指向下一層的頭節(jié)點，即可得到每層遍歷的起點
   • 再考慮用一個尾指針表示下一層的尾節(jié)點，則遍歷當前層時即可將下一層的節(jié)點接在尾節(jié)點上
2. 經(jīng)過上述分析，遍歷過程不再需要list容器，只需要3個指針即可，當前層遍歷指針，下一層頭指針及下一層尾指針
3. 每次遍歷完當前層，將下一層頭指針及尾指針重置

class Solution {public Node connect(Node root) {Node curTail = root;Node nextHead = null;Node nextTail = null;while (curTail != null) {// 看左子結點if (curTail.left != null) {if (nextTail != null) {nextTail.next = curTail.left;} else {nextHead = curTail.left;}nextTail = curTail.left;}// 看右子結點if (curTail.right != null) {if (nextTail != null) {nextTail.next = curTail.right;} else {nextHead = curTail.right;}nextTail = curTail.right;}if (curTail.next != null) {// 繼續(xù)當前層遍歷curTail = curTail.next;} else {// 當前層遍歷完畢，開啟下一層遍歷，將下一層指針重置curTail = nextHead;nextHead = null;nextTail = null;}}return root;}
}

其他非官方題解：

class Solution {public Node connect(Node root) {Node cur = root;while (cur != null) {Node dummy = new Node(0);Node p = dummy;while (cur != null) {if (cur.left != null) {p.next = cur.left;p = p.next;}if (cur.right != null) {p.next = cur.right;p = p.next;}cur = cur.next;}cur = dummy.next;}return root;}
}