力扣hot100简单题（三）

目前学到简单题，进行一个复习汇总。需要搞清楚目标是什么（输入和返回值），再考虑要去怎么实现（判断条件是什么、递归还是迭代、使用列表还是字典之类）。每个题目尽量至少两种方法，一种简单的另一种节省算力。这里只写代码的主要部分。刚开始会有一些难以理解，可以根据leecode提供的用例去推推看。使用语言python。

推荐搭配饲养员的视频食用更佳。http://【手把手带你刷Leetcode力扣｜各个击破数据结构和算法｜大厂面试必备技能【已完结】】https://www.bilibili.com/video/BV1sy4y1q79M?p=78&vd_source=88d4164d269215752602ee47f9fbd4c3

1. 21合并两个有序链表

需要一个空节点来遍历链表，使用迭代法更快。注意最后可能会存在没有遍历完的链表，直接接上就可以。最后返回的是空节点的下一个节点，也就是合并后的链表head。

时间复杂度O（m+n）,空间复杂度O（1）。

dummy = ListNode(0) #定义一个空节点 cur = dummy while list1 and list2: if list1.val <= list2.val: cur.next = list1 list1 = list1.next else: cur.next = list2 list2 = list2.next cur = cur.next cur.next = list1 if list1 else list2 #没有遍历完的直接接上 return dummy.next #返回空节点的下一节点，即合并链表的头节点

2. 94二叉树的中序遍历

二叉树必会的点，前序、中序和后序遍历（主要以根节点的遍历位置命名）。

两种方法：

递归法：终止条件，递推关系，自己调用自己。时间复杂度: O(n)，每个节点被访问一次。空间复杂度: O(h)，h 是树的高度。递归调用栈的深度取决于树的高度，最坏情况（链表）下为 O(n)。

ans = [] def dfs(node): if not node: return dfs(node.left) #遍历左子树 ans.append(node.val) #访问根节点 dfs(node.right) #遍历右子树 dfs(root) return ans

迭代法：使用栈。时间复杂度O（n）,空间复杂度O（h）。

ans = [] stack = [] cur = root while stack or cur: #当前节点不为空，或栈不为空时，说明还有节点未处理 if cur: #一直向左走，并将沿途节点入栈 stack.append(cur) cur = cur.left else: #左边走到底了，开始处理栈顶节点 cur = stack.pop() ans.append(cur.val) cur = cur.right return ans

3. 104二叉树的最大深度

对于任何一个节点，以该节点为根的子树的最大深度 =1 + max(左子树深度, 右子树深度)。

两种方法：

递归法，直接使用已经定义的函数MaxDepth。时间复杂度O（n）,空间复杂度O（h）。

def maxDepth(self, root: Optional[TreeNode]) -> int: if not root: return 0 left_depth = self.maxDepth(root.left) right_depth = self.maxDepth(root.right) return 1+max(left_depth, right_depth)

迭代法

if not root: return 0 stack = [(root, 1)] # (节点, 当前深度) max_depth = 0 while stack: node, cur_depth = stack.pop() if node: max_depth = max(max_depth, cur_depth) # 将左右子树压栈，深度+1 stack.append((node.right, cur_depth + 1)) stack.append((node.left, cur_depth + 1)) return max_depth