🌈你好呀！我是 山頂風景獨好
🎈歡迎踏入我的博客世界，能與您在此邂逅，真是緣分使然！😊
🌸愿您在此停留的每一刻，都沐浴在輕松愉悅的氛圍中。
📖這里不僅有豐富的知識和趣味橫生的內容等您來探索，更是一個自由交流的平臺，期待您留下獨特的思考與見解。🌟
🚀讓我們一起踏上這段探索與成長的旅程，攜手挖掘更多可能，共同進步！💪?

題目一：路徑總和 II（LeetCode 113）

題目分析：

給你二叉樹的根節點 root 和一個整數目標和 targetSum ，找出所有 從根節點到葉子節點 路徑總和等于給定目標和的路徑。葉子節點是指沒有子節點的節點。例如：輸入root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22，輸出[[5,4,11,2],[5,8,4,5]]。

解題思路：

回溯法：通過遞歸遍歷二叉樹，記錄從根節點到當前節點的路徑，當到達葉子節點且路徑和等于目標和時，將路徑加入結果集。
路徑記錄：使用列表存儲當前路徑上的節點值，遞歸進入子節點時添加節點值，回溯時移除節點值。
終止條件：當當前節點為葉子節點（左右子節點均為空）時，判斷路徑和是否等于目標和，若相等則保存路徑。

示例代碼：

# 二叉樹節點定義
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef pathSum(root, targetSum):result = []def backtrack(node, current_path, current_sum):if not node:return# 將當前節點加入路徑current_path.append(node.val)current_sum += node.val# 到達葉子節點且路徑和等于目標值if not node.left and not node.right:if current_sum == targetSum:result.append(current_path.copy())# 遞歸遍歷左右子樹backtrack(node.left, current_path, current_sum)backtrack(node.right, current_path, current_sum)# 回溯：移除當前節點current_path.pop()backtrack(root, [], 0)return result# 輔助函數：根據列表構建二叉樹（簡化版，僅用于測試）
def build_tree(values):if not values:return Noneroot = TreeNode(values[0])queue = [root]i = 1while queue and i < len(values):node = queue.pop(0)if values[i] is not None:node.left = TreeNode(values[i])queue.append(node.left)i += 1if i < len(values) and values[i] is not None:node.right = TreeNode(values[i])queue.append(node.right)i += 1return root# 測試示例
if __name__ == "__main__":# 構建示例二叉樹：[5,4,8,11,null,13,4,7,2,null,null,5,1]values = [5,4,8,11,None,13,4,7,2,None,None,5,1]root = build_tree(values)targetSum = 22result = pathSum(root, targetSum)print("路徑總和等于{}的路徑：".format(targetSum), result)  # 輸出：[[5,4,11,2],[5,8,4,5]]

代碼解析：

backtrack函數遞歸遍歷二叉樹，參數包括當前節點、當前路徑列表、當前路徑和。
每次進入節點時，將節點值加入路徑并更新路徑和；若為葉子節點且路徑和等于目標值，則復制當前路徑加入結果集。
遞歸遍歷左右子樹后，執行回溯操作（彈出當前節點值），確保路徑列表正確反映上層節點的路徑。
時間復雜度為O(n2)（n為節點數，最壞情況下每個節點都需復制路徑，路徑長度為O(n)），空間復雜度為O(n)（遞歸棧深度和路徑列表長度）。

題目二：顏色分類（LeetCode 75）

題目分析：

給定一個包含紅色、白色和藍色、共n個元素的數組nums，原地對它們進行排序，使得相同顏色的元素相鄰，并按照紅色、白色、藍色順序排列。我們使用整數0、1和2分別表示紅色、白色和藍色。必須在不使用庫內置的排序函數的情況下解決這個問題。例如：輸入nums = [2,0,2,1,1,0]，輸出[0,0,1,1,2,2]。

解題思路：

三指針法：使用三個指針（left、current、right）分別追蹤0的右邊界、當前遍歷位置、2的左邊界。
遍歷邏輯：

• 若current指向0，交換left和current的值，left和current同時右移（確保0在左側）；
• 若current指向1，無需交換，current右移；
• 若current指向2，交換current和right的值，right左移（確保2在右側），current不動（需重新檢查交換后的值）。
  終止條件：當current > right時，所有元素排序完成。

示例代碼：

def sortColors(nums):"""Do not return anything, modify nums in-place instead."""left = 0  # 0的右邊界（left左側全為0）current = 0  # 當前遍歷位置right = len(nums) - 1  # 2的左邊界（right右側全為2）while current <= right:if nums[current] == 0:# 交換0到左側nums[left], nums[current] = nums[current], nums[left]left += 1current += 1elif nums[current] == 1:# 1無需交換，直接移動currentcurrent += 1else:  # nums[current] == 2# 交換2到右側nums[current], nums[right] = nums[right], nums[current]right -= 1# 測試示例
if __name__ == "__main__":nums = [2,0,2,1,1,0]sortColors(nums)print("排序后的顏色數組：", nums)  # 輸出：[0,0,1,1,2,2]

代碼解析：

三指針分工明確，left確保左側全為0，right確保右側全為2，current負責遍歷中間的1（或待處理元素）。
通過一次遍歷完成排序，所有交換操作均在原數組上進行，無需額外空間。
時間復雜度為O(n)（僅遍歷一次數組），空間復雜度為O(1)（只使用三個指針變量），實現了原地排序。

題目三：驗證二叉搜索樹（LeetCode 98）

題目分析：

給你一個二叉樹的根節點 root ，判斷其是否是一個有效的二叉搜索樹。有效二叉搜索樹定義如下：

• 節點的左子樹只包含 小于 當前節點的數。
• 節點的右子樹只包含 大于 當前節點的數。
• 所有左子樹和右子樹自身必須也是二叉搜索樹。
  例如：輸入root = [2,1,3]，輸出true；輸入root = [5,1,4,null,null,3,6]，輸出false（4的左子樹包含3，小于5）。

解題思路：

中序遍歷：二叉搜索樹的中序遍歷結果是嚴格遞增的，可通過驗證中序遍歷序列是否遞增來判斷。
遞歸驗證：通過遞歸函數傳遞當前節點值的合法范圍（下界和上界），確保左子樹所有節點值小于當前節點值，右子樹所有節點值大于當前節點值。
邊界處理：使用負無窮和正無窮作為初始上下界，空樹視為有效的二叉搜索樹。

示例代碼：

# 二叉樹節點定義
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef isValidBST(root):def helper(node, lower, upper):# 空樹是有效的if not node:return True# 當前節點值必須在(lower, upper)范圍內val = node.valif val <= lower or val >= upper:return False# 左子樹的上界為當前節點值，右子樹的下界為當前節點值return helper(node.left, lower, val) and helper(node.right, val, upper)# 初始范圍為(-無窮, +無窮)return helper(root, float('-inf'), float('inf'))# 輔助函數：構建二叉樹（同題目一）
def build_tree(values):if not values:return Noneroot = TreeNode(values[0])queue = [root]i = 1while queue and i < len(values):node = queue.pop(0)if values[i] is not None:node.left = TreeNode(values[i])queue.append(node.left)i += 1if i < len(values) and values[i] is not None:node.right = TreeNode(values[i])queue.append(node.right)i += 1return root# 測試示例
if __name__ == "__main__":# 示例1：[2,1,3]root1 = build_tree([2,1,3])print("是否為有效二叉搜索樹1：", isValidBST(root1))  # 輸出：True# 示例2：[5,1,4,None,None,3,6]root2 = build_tree([5,1,4,None,None,3,6])print("是否為有效二叉搜索樹2：", isValidBST(root2))  # 輸出：False

代碼解析：

helper函數遞歸驗證每個節點是否在合法范圍內：左子樹的所有節點必須小于當前節點值（上界為當前節點值），右子樹的所有節點必須大于當前節點值（下界為當前節點值）。
初始調用時，下界為負無窮，上界為正無窮，確保根節點值合法。
若所有節點都滿足范圍約束，則返回true，否則返回false。
時間復雜度為O(n)（每個節點訪問一次），空間復雜度為O(n)（遞歸棧深度，最壞情況下為鏈狀樹）。

---

? 這就是今天要分享給大家的全部內容了，我們下期再見！😊
🏠 我在CSDN等你哦！我的主頁😍