leetcode230-二叉搜索树中第K小的元素

leetcode 230

思路

二叉搜索树特性

• 左子树所有节点的值均小于当前节点的值
• 右子树所有节点的值均大于当前节点的值
• 左右子树也分别是二叉搜索树

根据以上特性，使用中序遍历得到的结果就是从小到大排序的

具体思路如下：

1. 中序遍历：按照左 - 中 - 右的顺序遍历 二叉搜索树
2. 计数器：每次访问节点时将计数器减 1
3. 终止条件：当计数器减到 0 时，当前节点即为第 K 小的元素

实现

var kthSmallest = function (root, k) {let result;const deep = (root) => {// 终止条件if (!root || result !== undefined) return;// 左deep(root.left)// 中k--if (k === 0) {result = root.val}// 右deep(root.right)}deep(root)return result
};