在每个节点中填充下一个右侧节点指针的算法#
给定一个完美二叉树，其中所有叶子节点都在同一层级上，每个父节点都有两个子节点。二叉树的定义如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充每个节点的下一个右侧节点指针，如果没有下一个右侧节点，则将下一个指针设置为 NULL。
初始时，所有的下一个指针都被设置为 NULL。
示例 1：
输入: root = [1,2,3,4,5,6,7]
输出: [1,#,2,3,#,4,5,6,7,#]
解释：给定上述完美二叉树（图 A），你的函数应该填充每个节点的下一个右侧节点指针，就像图 B 中的一样。序列化输出按照连接的下一个指针的层次顺序排列，其中 '#' 表示每个层级的结束。
示例 2：
输入: root = []
输出: []
解法#
这题我不会，看了解法还是不懂，所以去找了个视频，POPULATING NEXT RIGHT POINTERS IN EACH NODE (Leetcode) - Code & Whiteboard，视频里讲的是 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
}
}