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

🟠   🔖  树 深度优先搜索 二叉搜索树 二叉树  🔗 力扣 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	二叉树的中序遍历	[✓]	栈 树 深度优先搜索 1+
671	二叉树中第二小的节点		树 深度优先搜索 二叉树