### 题目

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

Note: You may assume k is always valid, 1 < k < size.

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?

### 遍历二叉树，迭代版

• time: $O(n)$
• space: $O(n)$

#### 代码

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int kthSmallest(TreeNode root, int k) {
int count = 0;
Deque<TreeNode> stack = new LinkedList<>(); //已找到的待处理的左倾线上的节点
TreeNode cur = root; // 当前需要检查左倾线的节点（通常是右节点，除非是根节点）
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.offerFirst(cur);
cur = cur.left;
}
TreeNode node = stack.pollFirst(); count++; // count number
if (count == k) { return node.val; }
cur = node.right;
}
return 0; // never reached
}
}


### 遍历二叉树，递归版

• time: $O(n)$
• space: $O(1)$

#### 代码

public class Solution {
private int k = 0, order = 0, value = 0;
public int kthSmallest(TreeNode root, int k) {
init(k);
kth(root);
return value;
}
private void kth(TreeNode root) {
if (root == null) { return; }
kth(root.left);
if (order == k) { return; }
order++;
if (order == k) {
value = root.val; return;
}
kth(root.right);
}
private void init(int i) {
k = i; order = 0; value = 0;
}
}


### $O(\log_{}{n})$ 的二分查找无法实现，需要二叉树维护一个size参数

public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}