目前学到简单题进行一个复习汇总。需要搞清楚目标是什么输入和返回值再考虑要去怎么实现判断条件是什么、递归还是迭代、使用列表还是字典之类。每个题目尽量至少两种方法一种简单的另一种节省算力。这里只写代码的主要部分。刚开始会有一些难以理解可以根据leecode提供的用例去推推看。使用语言python。推荐搭配饲养员的视频食用更佳。http://【手把手带你刷Leetcode力扣各个击破数据结构和算法大厂面试必备技能【已完结】】https://www.bilibili.com/video/BV1sy4y1q79M?p78vd_source88d4164d269215752602ee47f9fbd4c31. 21合并两个有序链表需要一个空节点来遍历链表使用迭代法更快。注意最后可能会存在没有遍历完的链表直接接上就可以。最后返回的是空节点的下一个节点也就是合并后的链表head。时间复杂度Omn,空间复杂度O1。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迭代法使用栈。时间复杂度On,空间复杂度Oh。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 ans3. 104二叉树的最大深度对于任何一个节点以该节点为根的子树的最大深度 1 max(左子树深度, 右子树深度)。两种方法递归法直接使用已经定义的函数MaxDepth。时间复杂度On,空间复杂度Oh。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 1max(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