1. 二叉树展开为链表(114)#
代码语言：javascript
复制给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。
你可以使用原地算法（O(1) 额外空间）展开这棵树吗？
示例 1：
输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [0]
输出：[0]
代码语言：javascript
复制type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
/*
前序遍历 递归实现
时间复杂度：O(n)
空间复杂度：O(n)
*/
func flatten1(root *TreeNode) {
var preorderTraversal func(root *TreeNode) []*TreeNode
preorderTraversal = func(root *TreeNode) []*TreeNode {
var list []*TreeNode
if root != nil {
list = append(list, root)
list = append(list, preorderTraversal(root.Left)...)
list = append(list, preorderTraversal(root.Right)...)
}
return list
}
list := preorderTraversal(root)
for i := 1; i < len(list); i {
prev, cur := list[i-1], list[i]
prev.Left, prev.Right = nil, cur
}
}
/*
前序遍历 迭代实现
时间复杂度：O(n)
空间复杂度：O(n)
*/
func flatten2(root *TreeNode) {
var list []*TreeNode
var stack []*TreeNode
node := root
for node != nil || len(stack) > 0 {
for node != nil {
list = append(list, node)
stack = append(stack, node)
node = node.Left
}
node = stack[len(stack)-1]
node = node.Right
stack = stack[0 : len(stack)-1]
}
for i := 1; i < len(list); i {
prev, cur := list[i-1], list[i]
prev.Left, prev.Right = nil, cur
}
}
func main() {
}
2. 最长连续序列(128)#
代码语言：javascript
复制给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为O(n) 的算法解决此问题。
示例 1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2：
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9
由示例2可知重复的算同一个
代码语言：javascript
复制/*
哈希表
时间复杂度：O(n)
空间复杂度：O(n)
*/
func longestConsecutive(nums []int) int {
mp := make(map[int]bool)
for _, v := range nums {
mp[v] = true
}
var result int
for k, _ := range mp {
//最坏情况时间复杂度为O(n²)，在这里进行优化，
//即：只有当一个数是连续序列的第一个数的情况下才会进入内层循环
//如果一个k数前一个存在，则k的前一个数和k会组成连续的数，
//则会进入if的内循环for，则会多出很多不必要的枚举
//最终导致最坏情况时间复杂度为O(n²)
if !mp[k-1] {
curV := k
curLen := 1
for mp[curV 1] {
curV
curLen
}
if curLen > result {
result = curLen
}
}
}
return result
}
func main() {
nums := []int{0, 3, 7, 2, 5, 8, 4, 6, 0, 1}
fmt.Println(longestConsecutive(nums))
}
