二叉搜索树的递归定义：

  1. 是一棵空树
  2. 是一棵由根节点、左子树、右子树组成的树，同时左子树和右子树都是二叉搜索树，且左子树上所有节点的数据域都小于等于根节点的数据域，右子树上所有节点的数据域都大于等于根节点的数据域

满足以上两个条件之一的二叉树，就是二叉搜索树
从这个定义我们可以看出，二叉搜索树强调的是数据域的有序性。也就是说，二叉搜索树上的每一棵子树，都应该满足 左孩子 <= 根结点 <= 右孩子 这样的大小关系。

查找数据域为某一特定值的节点

假设这个目标节点点的数据域值为 n，我们借助二叉搜索树数据域的有序性，可以有以下查找思路：

  1. 递归遍历二叉树，若当前遍历到的结点为空，就意味着没找到目标结点，直接返回。
  2. 若当前遍历到的结点对应的数据域值刚好等于n，则查找成功，返回。
  3. 若当前遍历到的结点对应的数据域值大于目标值n，则应该在左子树里进一步查找，设置下一步的遍历范围为 root.left 后，继续递归。
  4. 若当前遍历到的结点对应的数据域值小于目标值n，则应该在右子树里进一步查找，设置下一步的遍历范围为 root.right 后，继续递归。
    1. function search(root, n) {
    2.  // 若 root 为空，查找失败，直接返回
    3.  if(!root) {
    4.      return 
    5.  }
    6.  // 找到目标结点，输出结点对象
    7.  if(root.val === n) {
    8.      console.log('目标结点是：', root)
    9.  } else if(root.val > n) {
    10.      // 当前结点数据域大于n，向左查找
    11.      search(root.left, n)
    12.  } else {
    13.      // 当前结点数据域小于n，向右查找
    14.      search(root.right, n)
    15.  }
    16. }

    插入新节点

    1. function insert(root, n) {
    2.  // 若 root 为空，说明当前是一个可以插入的空位
    3.  if(!root) { 
    4.      // 用一个值为n的结点占据这个空位
    5.      root = new TreeNode(n)
    6.      return 
    7.  }
    8.  // 查找成功，说明值为n的结点已经存在，不再重复创建，直接返回
    9.  if(root.val === n) {
    10.      return
    11.  } else if(root.val > n) {
    12.      // 当前结点数据域大于n，向左查找
    13.      insert(root.left, n)
    14.  } else {
    15.      // 当前结点数据域小于n，向右查找
    16.      insert(root.right, n)
    17.  }
    18. }

删除指定节点

  1. function delete(root, n) {
  2.     // 如果没找到目标结点，则直接返回
  3.     if(!root) {
  4.         return 
  5.     }
  6.     // 定位到目标结点，开始分情况处理删除动作
  7.     if(root.val === n) {
  8.         // 若是叶子结点，则不需要想太多，直接删除
  9.         if(!root.left && !root.right) {
  10.             root = null
  11.         } else if(root.left) {
  12.             // 寻找左子树里值最大的结点
  13.             const maxLeft = findMax(root.left)
  14.             // 用这个 maxLeft 覆盖掉需要删除的当前结点  
  15.             root.val = maxLeft.val
  16.             // 覆盖动作会消耗掉原有的 maxLeft 结点
  17.             delete(root.left, maxLeft.val)
  18.         } else {
  19.             // 寻找右子树里值最小的结点
  20.             const minRight = findMin(root.right)
  21.             // 用这个 minRight 覆盖掉需要删除的当前结点  
  22.             root.val = minRight.val
  23.             // 覆盖动作会消耗掉原有的 minRight 结点
  24.             delete(root.right, minRight.val)
  25.         }
  26.     } else if(root.val > n) {
  27.         // 若当前结点的值比 n 大，则在左子树中继续寻找目标结点
  28.         delete(root.left, n)
  29.     } else  {
  30.         // 若当前结点的值比 n 小，则在右子树中继续寻找目标结点
  31.         delete(root.right, n)
  32.     }
  33. }
  35. // 寻找左子树最大值
  36. function findMax(root) {
  37.     while(root.right) {
  38.         root = root.right
  39.     }
  40.     return root 
  41. }
  43. // 寻找右子树的最小值
  44. function findMin(root) {
  45.     while(root.left) {
  46.         root = root.left
  47.     }
  48.     return root
  49. }

二叉搜索树的验证

题目描述：给定一个二叉树，判断其是否是一个有效的二叉搜索树。 假设一个二叉搜索树具有如下特征： 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。

示例 1: 输入:

  1.         2
  2.    / \
  3.   1   3

输出: true

示例 2: 输入:

  1.         5
  2.    / \
  3.   1   4
  4.      / \
  5.     3   6

输出: false

解释: 输入为: [5,1,4,null,null,3,6]。 根节点的值为 5 ，但是其右子节点值为 4 。

  1. /**
  2.  * @param {TreeNode} root
  3.  * @return {boolean}
  4.  */
  5. const isValidBST = function(root) {
  6.   // 定义递归函数
  7.   function dfs(root, minValue, maxValue) {
  8.       // 若是空树，则合法
  9.       if(!root) {
  10.           return true
  11.       }
  12.       // 若右孩子不大于根结点值，或者左孩子不小于根结点值，则不合法
  13.       if(root.val <= minValue || root.val >= maxValue) return false
  14.       // 左右子树必须都符合二叉搜索树的数据域大小关系
  15.       return dfs(root.left, minValue,root.val) && dfs(root.right, root.val, maxValue)
  16.   }
  17.   // 初始化最小值和最大值为极小或极大
  18.   return dfs(root, -Infinity, Infinity)
  19. };

将排序数组转化为二叉搜索树

题目描述：将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例: 给定有序数组: [-10,-3,0,5,9], 一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

  1.             0
  2.      / \
  3.    -3   9
  4.    /   /
  5.  -10  5
  1. /**
  2.  * @param {number[]} nums
  3.  * @return {TreeNode}
  4.  */
  5. const sortedArrayToBST = function(nums) {
  6.     // 处理边界条件
  7.     if(!nums.length) {
  8.         return null
  9.     }
  11.     // root 结点是递归“提”起数组的结果
  12.     const root = buildBST(0, nums.length-1)
  14.     // 定义二叉树构建函数，入参是子序列的索引范围
  15.     function buildBST(low, high) {
  16.         // 当 low > high 时，意味着当前范围的数字已经被递归处理完全了
  17.         if(low > high) {
  18.             return null
  19.         }
  20.         // 二分一下，取出当前子序列的中间元素
  21.         const mid = Math.floor(low + (high - low)/2)  
  22.         // 将中间元素的值作为当前子树的根结点值
  23.         const cur = new TreeNode(nums[mid]) 
  24.         // 递归构建左子树，范围二分为[low,mid)
  25.         cur.left = buildBST(low,mid-1)
  26.         // 递归构建左子树，范围二分为为(mid,high]
  27.         cur.right = buildBST(mid+1, high)
  28.         // 返回当前结点
  29.         return cur
  30.     }
  31.     // 返回根结点
  32.     return root
  33. };