230. 二叉搜索树中第 K 小的元素
难度中等 338
给定一个二叉搜索树, 编写一个函数 kthSmallest 来查找其中第 k 个最小的元素.
说明:
你可以假设 k 总是有效的, 1 ≤ k ≤ 二叉搜索树元素个数.
示例 1:
输入: root = [3,1,4,null,2], k = 1
- 3
- / 1 4
- 2
输出: 1
示例 2:
输入: root = [5,3,6,2,4,null,null,1], k = 3
- 5
- / 3 6
- / 2 4
- /
- 1
输出: 3
进阶:
如果二叉搜索树经常被修改 (插入 / 删除操作) 并且你需要频繁地查找第 k 小的值, 你将如何优化 kthSmallest 函数?
方法一: 中序递归遍历
- class Solution {
- private int currentPos = 0;
- public int kthSmallest(TreeNode root, int k) {
- if (root == null) {
- return 0;
- }
- int leftValue = kthSmallest(root.left, k);
- if (leftValue != 0) {
- return leftValue;
- }
- // 访问根节点
- currentPos++;
- if (currentPos == k) {
- return root.val;
- }
- // 遍历右子树
- int rightValue = kthSmallest(root.right, k);
- if (rightValue != 0) {
- return rightValue;
- }
- return 0;
- }
- }
方法二: 中序非递归遍历
- public int kthSmallest(TreeNode root, int k) {
- if (root == null) {
- return -1;
- }
- Deque<TreeNode> stack = new LinkedList<>();
- TreeNode currentNode = root;
- while (currentNode != null || !stack.isEmpty()) {
- while (currentNode != null) {
- stack.push(currentNode);
- currentNode = currentNode.left;
- }
- // 访问根节点
- currentNode = stack.pop();
- k--;
- if (k == 0) {
- return currentNode.val;
- }
- // 遍历右子树
- currentNode = currentNode.right;
- }
- return -1;
- }
来源: http://www.bubuko.com/infodetail-3717168.html