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 result
42、将有序数组转换为二叉搜索树
给你一个整数数组 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 None
mid = len(nums) // 2
root = TreeNode(nums[mid])
root.left = sortedArrayToBST(nums[:mid])
root.right = sortedArrayToBST(nums[mid + 1:])
return root
43、验证二叉搜索树
给你一个二叉树的根节点 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 True
if not min_val < node.val < max_val:
return False
return isValid(node.left, min_val, node.val) and isValid(node.right, node.val, max_val)
return isValid(root, float('-inf'), float('inf')) # 对于根节点，它的上下限为无穷大和无穷小
