一、108. 将有序数组转换为二叉搜索树
- 思路：
每次将列表中点当作新的根节点，再将中点左右数组当作新的分支作递归判断。 - 代码：
class Solution:def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:if not nums:return Nonem = len(nums) // 2return TreeNode(nums[m], self.sortedArrayToBST(nums[:m]), self.sortedArrayToBST(nums[m + 1:]))
二、98. 验证二叉搜索树
- 思路：
分别检测左右子树是否为满足条件，再递归检测新的左右子树便可 - 代码：
class Solution:pre = -infdef isValidBST(self, root: Optional[TreeNode]) -> bool:if root is None:return Trueif not self.isValidBST(root.left) or root.val <= self.pre:return Falseself.pre = root.valreturn self.isValidBST(root.right)
三、230. 二叉搜索树中第 K 小的元素
- 思路：
使用中序遍历就是从小到大遍历节点值。 - 代码：
class Solution:def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:def dfs(cur):if not cur:returndfs(cur.left)res.append(cur.val)dfs(cur.right)res = []dfs(root)return res[k-1]
