前言
在上一篇文章《二叉树与前序遍历、中序遍历、后续遍历》中我们认识了二叉树。今天我们来认识一种特殊的二叉树结构 - 二叉搜索树。
二叉搜索树（BinarySearchTree）具备以下特点：
- 可能是一个空树；
- 可能是一个具备以下特点的二叉树：
a. 若左子树不为空，左子树所有节点的值均小于根节点的值； b. 若右子树不为空，右子树所有节点的值均大于根节点的值；
二叉搜索树又被称为二叉查找树、二叉排序树。
举个栗子🌰
使用变量声明一下。
// 定义节点类型 interface TreeNode { value: number; left: TreeNode | null; right: TreeNode | null; } // 定义二叉搜索树 const binarySearchTree: TreeNode = { value: 5, left: { value: 3, left: { value: 2, left: null, right: null, }, right: { value: 4, left: null, right: null, }, }, right: { value: 7, left: { value: 6, left: null, right: null, }, right: { value: 8, left: null, right: null, }, }, };
题目：二叉搜索树中第K小的元素
我们来分析分析题目，找出二叉搜索树中的第K小的元素，其实是相当于将二叉搜索树中的所有元素进行升序排序，取出第K个元素即可。
第一次遇到的同学可能没有头绪，或者会陷入直接思考取出每一个元素，每次都与排序数组中的数进行比较，然后进行插入排序操作，或者是考虑每次遍历所有元素取出一个最小值，依次取出K次。
虽然说这样都是可以实现的，但是性能这块儿是非常不理想的。在这里我们一定要清楚的认识到二叉搜索树的定义，二叉树中的节点，都遵循了这样的规律 “左子树所有节点的值均小于根节点的值，右子树所有节点的值均大于根节点的值” ===> left < root < right。
看到这里的时候，有的小伙伴可能心中已经有了实现的算法，是啥呢？换个角度看，
left -> root -> right，这个不就是中序遍历吗。如果我们定义一个数组arrSorted，中序遍历，依次放入二叉搜索树中的节点值，第k个最小值不就是arrSorted的第k个元素吗。
这里要注意
k的值取值时从0开始，还是从1开始。数组的下标是0开始的。
题目内容：给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。
Up Code~ 上代码~
// function kthSmallest (root: TreeNode | null, k: number): number { // 临界值判断 if (!root) return; // 升序数组 const arrSorted: number[] = []; // 中序遍历 const midOrderTraversal = (root: TreeNode | null) => { // 临界值判断 if (!root) return; // 注意顺序 // 1. 优先取left值 midOrderTraversal(root.left); // 2. 根节点值 arrSorted.push(root.value); // 3. right值 midOrderTraversal(root.right); }; // 中序遍历 midOrderTraversal(root); // 题目中的k是从1开始的，所以这个位置要-1 return arrSorted[k - 1]; }
调用下，看看
// arrSorted [2，3， 4， 5， 6， 7， 8] console.log(kthSmallest(binarySearchTree, 3)); // 4
非常完美~~~
结语
遇到二叉搜索树相关的面试题，一定要注意二叉搜索树的特点：left < root < right。二叉搜索树中的第k小的值或者是第k大的值都是一个意思。
