在每個節點中填充下一個右指針的演算法#
給定一個完美的二元樹，其中所有的葉子節點都在同一層，並且每個父節點都有兩個子節點。該二元樹具有以下定義：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
將每個 next 指針指向其下一個右節點。如果沒有下一個右節點，則 next 指針應該設置為 NULL。
最初，所有的 next 指針都被設置為 NULL。
範例 1：
輸入: root = [1,2,3,4,5,6,7]
輸出: [1,#,2,3,#,4,5,6,7,#]
解釋：給定上面的完美二元樹（圖 A），您的函數應該將每個 next 指針填充為指向其下一個右節點，就像圖 B 中的一樣。序列化的輸出按照 next 指針連接的層次順序，其中 '#' 表示每個層次的結束。
範例 2：
輸入: root = []
輸出: []
解法#
這個問題我不會，看了解法還是不懂，所以去找了個視頻，POPULATING NEXT RIGHT POINTERS IN EACH NODE (Leetcode) - Code & Whiteboard，視頻裡講的是 Python 的代碼，但是邏輯很清晰，翻譯成 Swift 也可以用。
簡單理解如下：
- 完美二元樹，所以有 left 一定有 right，故而遍歷時通過判斷 node.left 是否存在，即可知道是否有下一級
- 所有的 next 指針都被設置為 NULL，初始時所有 node 的 next 都是 nil
- 同一個父節點的 left 和 right 設置 next 關係，即 node.left.next = node.right，比如 2 和 3、4 和 5、6 和 7
- 不同父節點的設置 next 關係，則需要判斷父節點的 next 是否存在，存在則設置 node.right.next = node.next.left，比如 5 和 6
代碼如下：
/**
* Definition for a Node.
* public class Node {
* public var val: Int
* public var left: Node?
* public var right: Node?
* public var next: Node?
* public init(_ val: Int) {
* self.val = val
* self.left = nil
* self.right = nil
* self.next = nil
* }
* }
*/
class Solution {
func connect(_ root: Node?) -> Node? {
// 錯誤檢查
if root == nil {
return nil
}
var leftMostNode = root
// 遍歷左子樹
while (leftMostNode?.left != nil) {
var cur = leftMostNode
while (cur?.left != nil) {
cur?.left?.next = cur?.right
if (cur?.next != nil) {
cur?.right?.next = cur?.next?.left
}
cur = cur?.next
}
leftMostNode = leftMostNode?.left
}
return root
}
}