二叉搜索树

二叉搜索树，即 BST （Binary Search Tree）。我们先来看看它的定义：

二叉搜索树是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值。

从它的定义中，我们可以总结出它拥有的两个特性：

1. 对于 BST 的每一个节点 node，左子树节点的值都比 node 的值要小，右子树节点的值都比 node 的值大。
2. 对于 BST 的每一个节点 node，它的左侧子树和右侧子树都是 BST。

这是一个非常重要的数据结构设计。经过自平衡优化的 BST，如红黑树，AVL树，能够从增删改查各个方面全部实现 O(lgN) 级别的时间复杂度。

从它的两个特性我们可以注意到，它与我们在快速排序完成后的树形结构是一模一样的。也就是说，二叉搜索树的中序遍历结果一定是有序的。这个特性对我们解题的思路十分有帮助。

例如在 [230] 二叉搜索树中第K小的元素 中，我们需要在 BST 中找出第 K 小的元素。由于 BST 其中序遍历是有序的，因此题目就被直接简化成：输出中序遍历的第K个结果。题目就变得十分简单了。

function kthSmallest(root: TreeNode | null, k: number): number {
  let count = 0;
  let res = root.val;
  traverse(root);
  return res;

  function traverse(node: TreeNode | null) {
    if (!node) return;

    traverse(node.left);
    count += 1;
    if (count === k) {
      res = node.val;
      return;
    }
    traverse(node.right);
  }
}