LeetCode热题Top100 | 中等 | 下

给你二叉树的根结点 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]

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() {

}

给定一个未排序的整数数组 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可知重复的算同一个

/*
哈希表
时间复杂度：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))
}