特殊的二叉树-二叉搜索树

二叉搜索树（Binary Search Tree）简称 BST，是二叉树的一种特殊形式。

什么是二叉搜索树

树的定义总是以递归的形式出现，二叉搜索树也不例外，它的递归定义如下：

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

满足以上两个条件之一的二叉树，就是二叉搜索树。

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

二叉搜索树：编码基本功

关于二叉搜索树，大家需要掌握以下高频操作：

查找数据域为某一特定值的结点
插入新结点
删除指定结点

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

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

递归遍历二叉树，若当前遍历到的结点为空，就意味着没找到目标结点，直接返回。
若当前遍历到的结点对应的数据域值刚好等于 n，则查找成功，返回。
若当前遍历到的结点对应的数据域值大于目标值 n，则应该在左子树里进一步查找，设置下一步的遍历范围为 root.left 后，继续递归。
若当前遍历到的结点对应的数据域值小于目标值 n，则应该在右子树里进一步查找，设置下一步的遍历范围为 root.right 后，继续递归。

function search(root, n) {
  if (!root) return;
  if (root.val === n) return root;
  if (root.val < n) return search(root.right, n);
  if (root.val > n) return search(root.left, n);
}

插入新结点

从根结点开始，把我们希望插入的数据值和每一个结点作比较。若大于当前结点，则向右子树探索；若小于当前结点，则向左子树探索。最后找到的那个空位，就是它合理的栖身之所。

function insertIntoBST(root, n) {
  // 若 root 为空，说明当前是一个可以插入的空位
  if (!root) {
    // 用一个值为n的结点占据这个空位
    const node = new TreeNode(n);
    return node;
  }
  if (root.val < n) {
    // 当前结点数据域小于n，向右查找
    root.right = insertIntoBST(root.right, n);
  } else {
    // 当前结点数据域大于n，向左查找
    root.left = insertIntoBST(root.left);
  }
  // 返回插入后二叉搜索树的根结点
  return root;
}

删除指定结点

想要删除某个结点，首先要找到这个结点。在定位结点后，我们需要考虑以下情况：

结点不存在，定位到了空结点。直接返回即可。
需要删除的目标结点没有左孩子也没有右孩子——它是一个叶子结点，删掉它不会对其它结点造成任何影响，直接删除即可。
需要删除的目标结点存在左子树，那么就去左子树里寻找小于目标结点值的最大结点，用这个结点覆盖掉目标结点
需要删除的目标结点存在右子树，那么就去右子树里寻找大于目标结点值的最小结点，用这个结点覆盖掉目标结点
需要删除的目标结点既有左子树、又有右子树，这时就有两种做法了：要么取左子树中值最大的结点，要么取右子树中取值最小的结点。两个结点中任取一个覆盖掉目标结点，都可以维持二叉搜索树的数据有序性

function deleteNode(root, n) {
  // 如果没找到目标结点，则直接返回
  if (!root) {
    return root;
  }
  // 定位到目标结点，开始分情况处理删除动作
  if (root.val === n) {
    // 若是叶子结点，则不需要想太多，直接删除
    if (!root.left && !root.right) {
      root = null;
    } else if (root.left) {
      // 寻找左子树里值最大的结点
      const maxLeft = findMax(root.left);
      // 用这个 maxLeft 覆盖掉需要删除的当前结点
      root.val = maxLeft.val;
      // 覆盖动作会消耗掉原有的 maxLeft 结点
      root.left = deleteNode(root.left, maxLeft.val);
    } else {
      // 寻找右子树里值最小的结点
      const minRight = findMin(root.right);
      // 用这个 minRight 覆盖掉需要删除的当前结点
      root.val = minRight.val;
      // 覆盖动作会消耗掉原有的 minRight 结点
      root.right = deleteNode(root.right, minRight.val);
    }
  } else if (root.val > n) {
    // 若当前结点的值比 n 大，则在左子树中继续寻找目标结点
    root.left = deleteNode(root.left, n);
  } else {
    // 若当前结点的值比 n 小，则在右子树中继续寻找目标结点
    root.right = deleteNode(root.right, n);
  }
  return root;
}

// 寻找左子树最大值
function findMax(root) {
  while (root.right) {
    root = root.right;
  }
  return root;
}

// 寻找右子树的最小值
function findMin(root) {
  while (root.left) {
    root = root.left;
  }
  return root;
}

二叉搜索树的特性

关于二叉搜索树的特性，有且仅有一条是需要大家背诵默写的：

二叉搜索树的中序遍历序列是有序的！

判断一棵二叉树是不是二叉搜索树

题目描述：给定一个二叉树，判断其是否是一个有效的二叉搜索树。

空树的判定比较简单，关键在于非空树的判定：需要递归地对非空树中的左右子树进行遍历，检验每棵子树中是否都满足 左 <= 根 <= 右 这样的关系。基于这样的思路，我们可以编码如下：

function isValidBST(root) {
  function dfs(root, minValue, maxValue) {
    // 若是空树，则合法
    if (!root) {
      return true;
    }
    // 若右孩子不大于根结点值，或者左孩子不小于根结点值，则不合法
    if (root.val <= minValue || root.val >= maxValue) return false;
    // 左右子树必须都符合二叉搜索树的数据域大小关系
    return (
      dfs(root.left, minValue, root.val) && dfs(root.right, root.val, maxValue)
    );
  }
  // 初始化最小值和最大值为极小或极大
  return dfs(root, -Infinity, Infinity);
}

复盘

递归过程中，起到决定性作用的是这两个判定条件：

左孩子的值是否小于根结点值
右孩子的值是否大于根结点值

但是在上面的编码中我们采取了一种更简洁的手法，通过设置 minValue 和 maxValue 为极小和极大值，来确保 root.val <= minValue || root.val >= maxValue 这两个条件中有一个是一定为 false 的。

对特性的考察：将排序数组转化为二叉搜索树

题目描述：将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。

输入：[-10,-3,0,5,9]

输出：

      0
     / \
   -3   9
   /   /
 -10  5

思路分析

这个二叉树从形状上来看，像不像是把数组从 0 这个中间位置给“提起来”了？

为什么可以通过“提起来”来实现数组到目标二叉树的转换，这里面蕴含了两个依据：

二叉搜索树的特性：题目中指明了目标树是一棵二叉搜索树，二叉搜索树的中序遍历序列是有序的，题中所给的数组也是有序的，因此我们可以认为题目中给出的数组就是目标二叉树的中序遍历序列。中序遍历序列的顺序规则是左 -> 根 -> 右，因此数组中间位置的元素一定对应着目标二叉树的根结点。以根结点为抓手，把这个数组“拎”起来，得到的二叉树一定是符合二叉搜索树的排序规则的。
平衡二叉树的特性：虽然咱们还没有讲啥是平衡二叉树，但是题目中已经妥妥地给出了一个平衡二叉树的定义：

一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。

要做到这一点，只需要把“提起来”这个动作贯彻到底就行了：当我们以有序数组的中间元素为根结点，“提”出一个二叉树时，有两种可能的情况：

数组中元素为奇数个，此时以数组的中间元素为界，两侧元素个数相同：

[-10, -3, 0, 5, 9];

如果我们以中间元素为根结点，把数组“提”成二叉树，那么根结点左右两侧的元素个数是一样的，所以站在根结点来看，左右子树的高度差为 0：

数组中元素为偶数个，此时无论是选择中间靠左的元素为界、还是选择中间靠右的元素为界，两侧元素个数差值的绝对值都是 1：

[-10, -3, 0, 5];

在这个例子里，若以 -3 为根结点，那么左右子树的高度差的绝对值就是 1：

以 0 为根结点亦然。

通过对以上情况进行探讨，我们发现“以中间元素为根结点，将数组提成树”这种操作，可以保证根结点左右两侧的子树高度绝对值不大于 1。要想保证每一棵子树都满足这个条件，我们只需要对有序数组的每一个对半分出来的子序列都递归地执行这个操作即可。

/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
const sortedArrayToBST = function(nums) {
  // 处理边界条件
  if (!nums.length) {
    return null;
  }

  // root 结点是递归“提”起数组的结果
  const root = buildBST(0, nums.length - 1);

  // 定义二叉树构建函数，入参是子序列的索引范围
  function buildBST(low, high) {
    // 当 low > high 时，意味着当前范围的数字已经被递归处理完全了
    if (low > high) {
      return null;
    }
    // 二分一下，取出当前子序列的中间元素
    const mid = Math.floor(low + (high - low) / 2);
    // 将中间元素的值作为当前子树的根结点值
    const cur = new TreeNode(nums[mid]);
    // 递归构建左子树，范围二分为[low,mid)
    cur.left = buildBST(low, mid - 1);
    // 递归构建左子树，范围二分为为(mid,high]
    cur.right = buildBST(mid + 1, high);
    // 返回当前结点
    return cur;
  }
  // 返回根结点
  return root;
};

什么是二叉搜索树​

二叉搜索树：编码基本功​

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

插入新结点​

删除指定结点​

二叉搜索树的特性​

判断一棵二叉树是不是二叉搜索树​

复盘​

对特性的考察：将排序数组转化为二叉搜索树​

思路分析​