LeetCode 230 - Kth Smallest Element in a BST

作者 QIFAN 日期 2017-01-29
LeetCode 230 - Kth Smallest Element in a BST

原题链接: 230. Kth Smallest Element in a BST


题干

给定一个 BST ,要求返回第 k 个小的元素。
假设 k 都是有效的。

Follow up
如果 BST 的插入和删除操作很频繁,怎样可以优化查找?

思路

中序遍历

BST 的特点就是 左 < 中 < 右 ,是不是很像中序遍历?遍历到第 k 个就是要找的元素。

代码:

int visited = 0;
int res;
public int kthSmallest(TreeNode root, int k) {
inorder(root, k);
return res;
}
private void inorder(TreeNode node, int k) {
if (node == null) {
return;
}
inorder(node.left, k);
visited++;
if (visited == k) {
res = node.val;
}
inorder(node.right, k);
}

对于 Follow up ,可以在树节点加入一个属性表示比它大的有多少,比它小的有多少,然后在插入和删除的时候更新属性,那样查找可以一直保持在 $O(logN)$ ,也就是树的高度。