什么是二叉搜索树（BST）？

满足以下两个条件之一的就是BST：

是一棵空树
左子树的值<= 根结点的值 <= 右子树的值

BST的关键是数据的有序性，以下都是BST，可以看出BST的中序遍历结果是一个升序数组

关于BST的题目

关于BST的题目主要由递归+数据有序性来解

二叉搜索树中的搜索（LeetCode 700）

给定二叉搜索树（BST）的根节点和一个值。你需要在BST中找到节点值等于给定值的节点。返回以该节点为根的子树。如果节点不存在，则返回 NULL。

var searchBST = function(root, val) {
  if(!root){
    return root
  }
  if(val < root.val){
    return searchBST(root.left, val)
  }else if(val > root.val){
    return searchBST(root.right, val)
  }else{
    return root
  }
};

二叉搜索树中的插入操作（LeetCode 701）

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。输入数据保证新值和原始二叉搜索树中的任意节点值都不同。

思路分析：
插入新结点类似查找，查找到最后找不到的时候就可以插入新结点了

var insertIntoBST = function(root, val) {
  if(!root){ // 递归先写边界条件
    return new TreeNode(val)
  }
  if(val < root.val){
    root.left = insertIntoBST(root.left, val)
  }else{
    root.right = insertIntoBST(root.right, val)
  }
  return root
};

验证二叉搜索树（LeetCode 98）

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树

思路分析：
使用 Infinity 来辅助，只需要判断是不是在最小值和最大值之间

var isValidBST = function(root) {
  function dfs(root, min, max){
    if(!root){ // 空树有效，先写递归边界条件
      return true
    }
    if(root.val >= max || root.val <= min){
      return false
    }
    return dfs(root.left, min, root.val) && dfs(root.right, root.val, max)
  }
  return dfs(root, -Infinity, Infinity)
};

将有序数组转换为二叉搜索树（LeetCode 108）

给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵高度平衡二叉搜索树。

注：一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。
示例：
输入：[-10, -3, 0, 5, 9]
输出：

思路分析：

BST的有序性决定了其中序遍历的结果是一个升序数组，因此我们可以把题目给出的数组当成BST中序遍历的结果。

根据平衡二叉树的特性，左右子树的元素应该差不多，我们以数组中间的元素作为分割点把数组分成两部分，左边组成左子树，中间元素代表根结点，右边组成右子树，不断的对子数组进行递归形成子树，最后生成我们想要的BST

var sortedArrayToBST = function(nums) {
function buildBST(left, right){ // 根据数组的区间[left, right] 构建BST
  // 递归先写边界条件
  if(left > right){
    return null
  }
  const mid =  Math.floor(left + (right -left)/2) 
  const root = new TreeNode(nums[mid]) // 二分创建根节点
  root.left = buildBST(left, mid-1) // 创建左子树
  root.right = buildBST(mid+1, right)
  return root
}
return buildBST(0, nums.length-1)
};