230. Kth Smallest Element in a BST

Leetcode link

解题思路

求第 k 小的 BST，核心思路还是在于用中序的优先遍历，当找到第 k 个元素的时候，就是第 k 小的元素

C++

class Solution {
 private:
  // 题目规范 BST 元素最小是 0
  int res = -1;

 public:
  void dfs(TreeNode* node, int& k) {
    // k < 0 是为了剪枝
    if (node == nullptr || k < 0) {
      return;
    }
    dfs(node->left, k);
    // 找到第 k 小的数之后直接返回
    if (--k == 0) {
      res = node->val;
      return;
    }
    dfs(node->right, k);
  }
  int kthSmallest(TreeNode* root, int k) {
    dfs(root, k);
    return res;
  }
};

Javascript

var kthSmallest = function(root, k) {
    let res = -1;
    let count = 0

    const dfs = (node, k) => {
      // count > k 是为了剪枝
        if (!node || count > k) {
            return;
        }
        dfs(node.left, k);
      // 当找到第 k 小的数直接返回
        if (++count == k) {
            res = node.val;
            return;
        }
        dfs(node.right, k);
    }

    dfs(root, k);
    return res;
};