LeetCode 230.二叉搜索树中第K小的元素 - JavaScript

题目描述：给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

说明：你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。

# 解法：利用 BST 性质

根据二叉搜索树（BST）的性质：节点的权重大于左节点的权重，大于右节点的权重。因此，对 BST 进行中序遍历，就是按从小到大的顺序访问树中的元素。

解题关键是：在中序遍历过程中使用一个变量来记录当前节点被访问的次序。

代码如下：

// ac地址：https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/
// 原文地址：https://xxoo521.com/2020-03-05-kth-smallest-element-in-a-bst/
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function(root, k) {
  let i = 0;
  let val = null;
  travel(root);
  return val;

  function travel(node) {
    node.left && travel(node.left);

    if (++i === k) {
      val = node.val;
      return;
    }

    node.right && travel(node.right);
  }
};

# 更多资料

若有错误，欢迎指正。若对您有帮助，请给个「关注+点赞」，您的支持是我更新的动力 👇

• 📖Blog：剑指 Offer + Leetcode 题解
• 🐱Github ：https://github.com/dongyuanxin/blog
• 🌟 公众号：心谭博客