示例 1:
输入:
[[1,3],[2,6],[8,10],[15,18]]
输出:
[[1,6],[8,10],[15,18]]
解释:
区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入:
[[1,4],[4,5]]
输出:
[[1,5]]
解释:
区间 [1,4] 和 [4,5] 可被视为重叠区间。
合并区间[a, b]可以采用：排序->拼接 的方法
排序：以a从小到大，a相同，以b从小到大排序
拼接：以拼接结果最后一个区间的lb为基准，如果下一个na大于lb，直接拼接；如果下一个nb大于lb，则lb=nb。
func merge(_ intervals: [[Int]]) -> [[Int]] {
if intervals.count <= 1 { return intervals }
let sorted = intervals.sorted { $0[0] == $1[0] ? $0[1] < $1[1] : $0[0] < $0[1] }
var merged: [[Int]] = [[sorted[0][0], sorted[0][1]]]
for index in (1..<sorted.count) {
let item = sorted[index]
let last = merged[merged.count - 1]
if last[1] + 1 < item[0] {
merged.append(item)
}
else if last[1] < item[1] {
merged[merged.count - 1] = [last[0], item[1]]
}
}
return merged
}
输入：
[1, null, 2, 3]
输出：
1, 3, 2
默认递归
func inorderTraversal(_ root: TreeNode?) -> [Int] {
guard let root = root else { return [] }
var result = [Int]()
result += inorderTraversal(root.left)
result.append(root.val)
result += inorderTraversal(root.right)
return result
}
迭代思考：
左侧的节点必定先于右侧的节点输出，所以对于任一子树，首先查找它最左侧的叶子节点，并且把这一路上经过的所有节点依次压入栈中。从栈中弹出一个节点输出它的值，再进入它的右节点。重复上述步骤。
func inorderTraversal(_ root: TreeNode?) -> [Int] {
var stack = [TreeNode]()
var result = [Int]()
var node = root
while node != nil || !stack.isEmpty {
while node != nil { // 这时node有可能是右节点，主要还是左节点
stack.append(node!)
node = node!.left
}
node = stack.popLast()
result.append(node!.val)
node = node?.right
}
return result
}
