41、二叉樹的層序遍歷
給你二叉樹的根節點 root ，返回其節點值的 層序遍歷 。 （即逐層地，從左到右訪問所有節點）。
示例 1：
輸入：root = [3,9,20,null,null,15,7]
輸出：[[3],[9,20],[15,7]]示例 2：
輸入：root = [1]
輸出：[[1]]示例 3：
輸入：root = []
輸出：[]提示：
- 樹中節點數目在范圍
[0, 2000]內 -1000 <= Node.val <= 1000
思路解答：
- 使用隊列來存儲每一層的節點，實現層序遍歷。
- 從根節點開始，將根節點入隊。然后循環遍歷隊列，每次取出隊列中的節點，將其值加入結果列表，并將其非空子節點依次入隊。
- 重復這個過程直到隊列為空，即遍歷完整棵樹。
- 返回層序遍歷的結果列表。
def levelOrder(self, root: Optional[TreeNode]) -> list[list[int]]:if not root:return []queue = collections.deque([root])result = []while queue:level_vales = []for _ in range(len(queue)):node = queue.popleft()level_vales.append(node.val)if node.left:queue.append(node.left)if node.right:queue.append(node.right)result.append(level_vales)return result42、將有序數組轉換為二叉搜索樹
給你一個整數數組 nums ，其中元素已經按 升序 排列，請你將其轉換為一棵 高度平衡 二叉搜索樹。
高度平衡 二叉樹是一棵滿足「每個節點的左右兩個子樹的高度差的絕對值不超過 1 」的二叉樹。
示例 1：
輸入：nums = [-10,-3,0,5,9]
輸出：[0,-3,9,-10,null,5]
解釋：[0,-10,5,null,-3,null,9] 也將被視為正確答案：
示例 2：
輸入：nums = [1,3]
輸出：[3,1]
解釋：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索樹。提示：
1 <= nums.length <= 104-104 <= nums[i] <= 104nums按 嚴格遞增 順序排列
思路解答：
- 選擇根節點： 由于數組是升序排列的，可以選擇中間元素作為根節點，這樣可以保持樹的高度平衡。
- 遞歸構建左右子樹： 將數組分為左右兩部分，分別遞歸構建左子樹和右子樹。
- 返回根節點： 最終返回根節點。
def sortedArrayToBST(self, nums: list[int]) -> Optional[TreeNode]:if not nums:return Nonemid = len(nums) // 2root = TreeNode(nums[mid])root.left = sortedArrayToBST(nums[:mid])root.right = sortedArrayToBST(nums[mid + 1:])return root43、驗證二叉搜索樹
給你一個二叉樹的根節點 root ，判斷其是否是一個有效的二叉搜索樹。
有效 二叉搜索樹定義如下：
- 節點的左子樹只包含 小于 當前節點的數。
- 節點的右子樹只包含 大于 當前節點的數。
- 所有左子樹和右子樹自身必須也是二叉搜索樹。
示例 1：
輸入：root = [2,1,3]
輸出：true示例 2：
輸入：root = [5,1,4,null,null,3,6]
輸出：false
解釋：根節點的值是 5 ，但是右子節點的值是 4 。提示：
- 樹中節點數目范圍在
[1, 104]內 -231 <= Node.val <= 231 - 1
思路解答：
- 遞歸遍歷： 通過遞歸遍歷二叉樹，同時傳遞當前節點應該滿足的最小值和最大值范圍。
- 判斷條件： 在遞歸過程中，對于每個節點，判斷其值是否在當前的最小值和最大值范圍內。
- 返回結果： 如果所有節點都滿足二叉搜索樹的條件，則返回True；否則返回False。
def isValidBST(self, root: Optional[TreeNode]) -> bool:def isValid(node, min_val, max_val):if not node: return Trueif not min_val < node.val < max_val: return Falsereturn isValid(node.left, min_val, node.val) and isValid(node.right, node.val, max_val)return isValid(root, float('-inf'), float('inf')) # 對于根節點，它的上下限為無窮大和無窮小
