前言
- 又是新的一周，快樂的周一，快樂地刷題，今天把鏈表搞完再干活！
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
-
?后言
- 搞定二叉樹咯，頭好暈啊，肯定是天氣凍的，晚上再簡單干點活就可以玩耍咯
