LeetCode 230. Kth Smallest Element in a BST

题目：

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

 

Example 1:

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

Example 2:

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

Follow up: What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

 

Constraints:

The number of elements of the BST is between 1 to 10^4.You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

---

这道题其实可以被inorder traversal覆盖。最简单的办法就是递归inorder得到结果，然后取出第k个，时间空间都是O(n)。另外如果借鉴iterative的做法，可以不用全部traverse完就能得到第k个，所以更省时间。完全就是inorder的做法（https://blog.csdn.net/qq_37333947/article/details/105853116）。时间复杂度据说是平均O(logn)最坏unbalanced是O(n)，空间同O(logn)。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Kth Smallest Element in a BST.

Memory Usage: 38.5 MB, less than 12.23% of Java online submissions for Kth Smallest Element in a BST.

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public int kthSmallest(TreeNode root, int k) { if (root == null) { return 0; } Deque<TreeNode> stack = new ArrayDeque<>(); pushLeft(root, stack); int count = 0; while (!stack.isEmpty()) { TreeNode node = stack.pop(); count++; if (count == k) { return node.val; } pushLeft(node.right, stack); } return -1; } private void pushLeft(TreeNode root, Deque<TreeNode> stack) { TreeNode curr = root; while (curr != null) { stack.push(curr); curr = curr.left; } } }