演算法_填充每個節點的右側指針#
你有一棵完美的二叉樹，所有葉子都在同一層，每個父節點都有兩個子節點。這棵二叉樹的定義如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充每個下一個指針，使其指向其右側的下一個節點。如果沒有右側的下一個節點，則下一個指針應設置為 NULL。
最初，所有的下一個指針都設置為 NULL。
範例 1：
Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
解釋：給定上述完美的二叉樹（圖 A），你的函數應該填充每個下一個指針，使其指向其右側的下一個節點，就像圖 B 中那樣。序列化輸出按層級順序連接，'#' 表示每一層的結束。
範例 2：
Input: root = []
Output: []
解法#
這題我不會，看了解法還是不懂，所以去找了個視頻，填充每個節點的右側指針 (Leetcode) - 代碼與白板，視頻裡講的是 Python 的代碼，但是邏輯很清晰，翻譯成 Swift 也可以用。
簡單理解如下：
- 完美的二叉樹，所以有左子節點一定有右子節點，故而遍歷時通過判斷 node.left 是否存在，即可知道是否有下一级
- 所有下一個指針都設置為 NULL，初始時所有 node 的 next 都是 nil
- 同一個父節點的左和右設置 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
}
}