共计 3222 个字符，预计需要花费 9 分钟才能阅读完成。
第一题 相交链表
题目
解题思路
哈希查找
func getIntersectionNode(headA, headB *ListNode) *ListNode {vis := map[*ListNode]bool{}
// 将链表 A 的节点存入哈希表中
for tmp := headA; tmp != nil; tmp = tmp.Next {vis[tmp] = true
}
// 在哈希表中搜寻链表 B 的第一个雷同节点
for tmp := headB; tmp != nil; tmp = tmp.Next {if vis[tmp] {return tmp}
}
return nil
}复杂度剖析
工夫复杂度：O(m+n)，其中 m 和 n 是别离是链表 headA 和 headB 的长度。须要遍历两个链表各一次。
空间复杂度：O(m)，其中 m 是链表 headA 的长度。须要应用哈希汇合存储链表 headA 中的全副节点。
双指针
func getIntersectionNode(headA, headB *ListNode) *ListNode {
if headA == nil || headB == nil {return nil}
pa, pb := headA, headB
for pa != pb {// 退出循环的条件为找到雷同的节点或实现第二遍遍历，两者皆为空
if pa == nil {pa = headB} else {pa = pa.Next}
if pb == nil {pb = headA} else {pb = pb.Next}
}
return pa
}复杂度剖析
工夫复杂度：O(m+n)，其中 m 和 n 是别离是链表 headA 和 headB 的长度。两个指针同时遍历两个链表，每个指针遍历两个链表各一次。
空间复杂度：O(1)。
另一种思路
func getIntersectionNode(headA, headB *ListNode) *ListNode {
// 判断谁更长，长多少
la, lb := length(headA), length(headB)
first, last, diff := headA, headB, la-lb
if la < lb {first, last, diff = last, first, lb-la}
// 长的先走
for i := 0; i < diff; i++ {first = first.Next}
// 一起往前走
for first != nil {
if first == last {return first}
first = first.Next
last = last.Next
}
return nil
}
func length(head *ListNode) (i int) {
for head != nil {
i++
head = head.Next
}
return
}
作者：arranger-core
链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/solution/go-chang-gui-si-lu-dui-qi-qi-dian-by-huweicai/
起源：力扣（LeetCode）著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。复杂度剖析
工夫复杂度：O(m+n+l)，其中 m 和 n 是别离是链表 headA 和 headB 的长度。获取链表长度须要对链表进行遍历。l 为较长链表到雷同节点的长度，最坏状况即无雷同节点时也需遍历整个链表。
空间复杂度：O(1)。
第二题 二叉树的中序遍历
题目
解题思路
递归
对于深搜 递归调用函数对子树进行操作天然是最简略的解法
用函数值使代码更为简洁易懂
func inorderTraversal(root *TreeNode) (res []int) {// 将变量 inorder 申明为 func() 类型，此时 inorder 就被俗称为“回调函数”，此时 inorder 的值为 nil。var inorder func(node *TreeNode)
// 函数值
inorder = func(node *TreeNode) {
if node == nil {return}
左根右中序遍历
inorder(node.Left)
res = append(res, node.Val)
inorder(node.Right)
}
// 对根节点进行操作
inorder(root)
return
}迭代
func inorderTraversal(root *TreeNode) (res []int) {stack := []*TreeNode{}
for root != nil || len(stack) > 0 {
for root != nil {stack = append(stack, root)
root = root.Left
}
root = stack[len(stack)-1]
stack = stack[:len(stack)-1]
res = append(res, root.Val)
root = root.Right
}
return
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/er-cha-shu-de-zhong-xu-bian-li-by-leetcode-solutio/
起源：力扣（LeetCode）著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。具体过程见官解视频，
复杂度剖析
工夫复杂度：O(n)，其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被拜访一次且只会被拜访一次。
空间复杂度：O(n)。空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的状况下会达到 O(n) 的级别。
Morris 中序遍历
将左子树的最初一个节点连贯到根节点上成为他的前缀，这样便可在遍历的时候一口气实现对树的遍历而不须要保护栈，升高了空间复杂度
func inorderTraversal(root *TreeNode) (res []int) {
for root != nil {
if root.Left != nil {
// predecessor 节点示意以后 root 节点向左走一步，而后始终向右走至无奈走为止的节点
predecessor := root.Left
for predecessor.Right != nil && predecessor.Right != root {
// 有右子树且没有设置过指向 root，则持续向右走
predecessor = predecessor.Right
}
if predecessor.Right == nil {
// 将 predecessor 的右指针指向 root，这样前面遍历完左子树 root.Left 后，就能通过这个指向回到 root
predecessor.Right = root
// 遍历左子树
root = root.Left
} else { // predecessor 的右指针曾经指向了 root，则示意左子树 root.Left 曾经拜访完了
res = append(res, root.Val)
// 复原原样
predecessor.Right = nil
// 遍历右子树
root = root.Right
}
} else { // 没有左子树
res = append(res, root.Val)
// 若有右子树，则遍历右子树
// 若没有右子树，则整颗左子树已遍历完，root 会通过之前设置的指向回到这颗子树的父节点
root = root.Right
}
}
return
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/er-cha-shu-de-zhong-xu-bian-li-by-leetcode-solutio/
起源：力扣（LeetCode）著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。复杂度剖析
工夫复杂度：O(n)，其中 n 为二叉搜寻树的节点个数。Morris 遍历中每个节点会被拜访两次，因而总工夫复杂度为 O(2n)=O(n)。
空间复杂度：O(1)
正文完
