算法闲两题

力扣：合并区间

示例 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

}