【力扣hot100】刷题笔记Day14

前言

又是新的一周，快乐的周一，快乐地刷题，今天把链表搞完再干活！

114. 二叉树展开为链表 - 力扣（LeetCode）

前序遍历

class Solution:def flatten(self, root: Optional[TreeNode]) -> None:if not root:returnst = [root]pre = Nonewhile st:cur = st.pop()# 把当前遍历结点接到上一个遍历结点上if pre:pre.left = Nonepre.right = cur  if cur.right:st.append(cur.right)if cur.left:st.append(cur.left)pre = curreturn root

前驱结点

class Solution:def flatten(self, root: Optional[TreeNode]) -> None:cur = rootwhile cur:pre = curif cur.left:cur = cur.leftwhile cur.right:cur = cur.right  # cur指向pre左子树的最右（前驱）cur.right = pre.right  # pre右子树接在前驱上pre.right = pre.left  # pre左子树移到右子树pre.left = None  # pre左指针置为Nonecur = pre.right  # cur继续往右return root

105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）

递归：复制数组O(n2)

class Solution:def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:if not preorder:return Noneroot = TreeNode(preorder[0])  # 构造根节点idx = inorder.index(preorder[0])  # 找到根节点在中序中的idx，O(n)root.left = self.buildTree(preorder[1: idx+1], inorder[0: idx])  # 递归构造左子树root.right = self.buildTree(preorder[idx+1:], inorder[idx+1:])   # 递归构造右子树return root

递归：数组下标+哈希O(n)

class Solution:def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:def dfs(i, l, r):if r - l < 0:return None  # 子树区间为空时终止root = TreeNode(preorder[i])  # 初始化根节点m = inorder_map[preorder[i]]  # 查询 m ，从而划分左右子树root.left = dfs(i + 1, l, m - 1)  # 子问题：构建左子树root.right = dfs(i + 1 + m - l, m + 1, r)  # 子问题：构建右子树return root      # 回溯返回根节点# 初始化哈希表，存储 inorder 元素到索引的映射inorder_map = {val: i for i, val in enumerate(inorder)}root = dfs(0, 0, len(inorder) - 1)return root

迭代

比较难理解和模拟，可以只记上面的递归方法即可，参考官解

class Solution:def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:if not preorder:return Noneroot = TreeNode(preorder[0])stack = [root]inorderIndex = 0for i in range(1, len(preorder)):preorderVal = preorder[i]node = stack[-1]if node.val != inorder[inorderIndex]:node.left = TreeNode(preorderVal)stack.append(node.left)else:while stack and stack[-1].val == inorder[inorderIndex]:node = stack.pop()inorderIndex += 1node.right = TreeNode(preorderVal)stack.append(node.right)return root

437. 路径总和 III - 力扣（LeetCode）

双重递归

两种方法思路参考题解

class Solution:# 求包含与不包含root的所有路径中满足要求的路径数def pathSum(self, root: TreeNode, sum: int) -> int:if not root:return 0return self.dfs(root, sum) + self.pathSum(root.left, sum) + self.pathSum(root.right, sum)# 求包含root的所有路径中满足要求的路径数    def dfs(self, root, path):if not root:return 0path -= root.valreturn (1 if path==0 else 0) + self.dfs(root.left, path) + self.dfs(root.right, path)

前缀和 + 哈希

class Solution:def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:prefixSumTree = {0:1}  # 前缀和：个数self.count = 0  # 答案prefixSum = 0  # 记录当前前缀和self.dfs(root, sum, prefixSum, prefixSumTree)return self.countdef dfs(self, root, targetSum, prefixSum, prefixSumTree):if not root:return 0prefixSum += root.valoldSum = prefixSum - targetSum  # 之前可能存在的等于目标和的路径和=当前前缀和-目标和if oldSum in prefixSumTree:self.count += prefixSumTree[oldSum]  # 存在的话结果加上路径数prefixSumTree[prefixSum] = prefixSumTree.get(prefixSum, 0) + 1  # 如果不用collections.defaultdict，键不存在就返回默认值0，再+1self.dfs(root.left, targetSum, prefixSum, prefixSumTree)self.dfs(root.right, targetSum, prefixSum, prefixSumTree)'''一定要注意在递归回到上一层的时候要把当前层的prefixSum的个数-1，类似回溯，要把条件重置'''prefixSumTree[prefixSum] -= 1

236. 二叉树的最近公共祖先 - 力扣（LeetCode）

递归后序

class Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':if not root or root == p or root == q:return rootleft = self.lowestCommonAncestor(root.left, p, q)right = self.lowestCommonAncestor(root.right, p, q)if left and right: return root  # 找到祖先了if not left: return right   # 一边没有就返回另一边if not right: return left

124. 二叉树中的最大路径和 - 力扣（LeetCode）

递归后序

class Solution:def maxPathSum(self, root: Optional[TreeNode]) -> int:self.maxSum = -float('inf')  # 以防路径是负值# 递归计算左右子节点的最大贡献值def maxGain(node):if not node:return 0leftGain = maxGain(node.left)    # 左贡献rightGain = maxGain(node.right)  # 右贡献newPath = leftGain + rightGain + node.val  # 最大路径 = 左右贡献值+当前值self.maxSum = max(self.maxSum, newPath)  # 更新答案return max(max(leftGain, rightGain) + node.val, 0)  # 返回贡献值，为负数就不贡献了maxGain(root)return self.maxSum