230. Kth Smallest Element in a BST

🟠   🔖  树 深度优先搜索 二叉搜索树 二叉树  🔗 LeetCode

题目

Given the root of a binary search tree, and an integer k, return thekth smallest value ( 1-indexed ) of all the values of the nodes in the tree.

Example 1:

Input: root = [3,1,4,null,2], k = 1

Output: 1

Example 2:

Input: root = [5,3,6,2,4,null,null,1], k = 3

Output: 3

Constraints:

• The number of nodes in the tree is n.
• 1 <= k <= n <= 10^4
• 0 <= Node.val <= 10^4

Follow up: If the BST is modified often (i.e., we can do insert and delete operations) and you need to find the kth smallest frequently, how would you optimize?

题目大意

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

解题思路

BST 的中序遍历结果是升序的，所以用一个外部变量记录中序遍历结果，第 k 个元素即是第 k 小的元素。

需要注意 i++ 要在 return 之前执行，否则会导致返回正确节点的父节点。

代码

/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function (root, k) {
  let i = 0;
  let res;
  const traverse = (root) => {
    if (!root) return null;
    traverse(root.left);
    i++;
    if (i == k) {
      res = root.val;
      return;
    }
    traverse(root.right);
  };
  traverse(root);
  return res;
};

相关题目

相关题目

• 94. 二叉树的中序遍历
• 671. 二叉树中第二小的节点

- [94. 二叉树的中序遍历](./0094.md)
- [671. 二叉树中第二小的节点](https://leetcode.com/problems/second-minimum-node-in-a-binary-tree)