二叉搜索树中第K小的元素
给定一个二叉搜索树的根节点 root
,和一个整数 k
,请你设计一个算法查找其中第 k
小的元素(从 1 开始计数)。
示例 1:

1 2
| 输入:root = [3,1,4,null,2], k = 1 输出:1
|
示例 2:

1 2
| 输入:root = [5,3,6,2,4,null,null,1], k = 3 输出:3
|
提示:
- 树中的节点数为
n
。
1 <= k <= n <= 104
0 <= Node.val <= 104
进阶:如果二叉搜索树经常被修改(插入/删除操作)并且你需要频繁地查找第 k
小的值,你将如何优化算法?
因为二叉搜索树的中序遍历是有序的,所以使用中序遍历处理。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| class Solution { int max = 10010; TreeNode[] stack = new TreeNode[max]; int top = 0;
public int kthSmallest(TreeNode root, int k) { while (top != 0 || root != null) { if (root != null) { stack[top++] = root; root = root.left; } else { root = stack[--top]; if (--k == 0) { break; } root = root.right; } } return root.val; } }
|
使用递归,设置一个计数器,访问到根节点时,计数器+1,计数器等于k
时,root.val
就是答案
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
|
class Solution { private int count = 0; private int ans = 0;
public int kthSmallest(TreeNode root, int k) { inorder(root, k); return ans; }
private void inorder(TreeNode root, int k) { if (root == null) { return; } inorder(root.left, k); if (++count == k) { ans = root.val; return; } inorder(root.right, k); } }
|