230. Kth Smallest Element in a BST

  • 42.7%

https://leetcode.com/problems/kth-smallest-element-in-a-bst/#/description

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 ≤ BST’s total elements.

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?

Hint:

  1. Try to utilize the property of a BST.
  2. What if you could modify the BST node’s structure?
  3. The optimal runtime complexity is O(height of BST).

中序遍历后,BST的结果是从小至大排列的。

方法一:中序遍历,保存至数组,然后取第k个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
vector<int> res;
inorder(root, res);
return res[k-1];
}

void inorder(TreeNode* root, vector<int>& res){
if(root){
inorder(root->left, res);
res.push_back(root->val);
inorder(root->right, res);
}
}
};

我的代码实现:

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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
vector<int> res;
inorder(root, res);
if(k<0 || k>res.size())
return -1;
return res[k-1];
}

void inorder(TreeNode* root, vector<int>& res){
if(root){
inorder(root->left, res);
res.push_back(root->val);
inorder(root->right, res);
}
}
};

方法二:

传入参数引用, 一次遍历。

1
2
3
4
5
6
7
8
9
int kthSmallest(TreeNode* root, int k) {
return find(root, k);
}
int find(TreeNode* root, int& k) {
if (root) {
int x = find(root->left, k);
return !k ? x : !--k ? root->val : find(root->right, k);
}
}

我的代码实现:

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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
return helper(root, k); // heler函数就是找到第k个并返回
}

int helper(TreeNode* root, int& k){
if(root){
int x = helper(root->left, k);
if(k==0)
return x;
else if(--k==0)
return root->val;
else
return helper(root->right, k);
}
return -1;
}
};

https://discuss.leetcode.com/topic/17573/4-lines-in-c

4 Lines in C++.

Go inorder and decrease k at each node. Stop the whole search as soon as k is zero, and then the k-th element is immediately returned all the way to the recursion top and to the original caller.

Try the left subtree first. If that made k zero, then its answer is the overall answer and we return it right away. Otherwise, decrease k for the current node, and if that made k zero, then we return the current node’s value right away. Otherwise try the right subtree and return whatever comes back from there.

1
2
3
4
5
6
int kthSmallest(TreeNode* root, int& k) {
if (root) {
int x = kthSmallest(root->left, k);
return !k ? x : !--k ? root->val : kthSmallest(root->right, k);
}
}

You might notice that I changed k from int to int& because I didn’t feel like adding a helper just for that and the OJ doesn’t mind. Oh well, here is that now:

1
2
3
4
5
6
7
8
9
int kthSmallest(TreeNode* root, int k) {
return find(root, k);
}
int find(TreeNode* root, int& k) {
if (root) {
int x = find(root->left, k);
return !k ? x : !--k ? root->val : find(root->right, k);
}
}

https://discuss.leetcode.com/topic/18689/share-my-c-iterative-alg

Share my C++ iterative ALG.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
stack<TreeNode *> st;
TreeNode *p = root;
while(p || !st.empty())
{
while(p)
{
st.push(p);
p = p->left;
}
p = st.top();
if(--k == 0)
return p->val;
st.pop();
p = p->right;
}
}
};

https://discuss.leetcode.com/topic/17577/c-solution-using-in-order-traversal

C++ solution using in order traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
void inorder(TreeNode* root, vector<int> &res){
if(!root)
return;
inorder(root->left, res);
res.push_back(root->val);
inorder(root->right,res);

}
int kthSmallest(TreeNode* root, int k) {
if(!root)
return -1;
vector<int> arr;
inorder(root, arr);
return arr[k-1];

}
};

108ms, 27.49%, June.17th, 2016

https://leetcode.com/discuss/44731/pythonic-approach-with-generator

Pythonic approach with generator

With generator in python, one very straightforward solution might be:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
# @param {TreeNode} root
# @param {integer} k
# @return {integer}
def kthSmallest(self, root, k):
for val in self.inorder(root):
if k == 1:
return val
else:
k -= 1

def inorder(self, root):
if root is not None:
for val in self.inorder(root.left):
yield val
yield root.val
for val in self.inorder(root.right):
yield val

https://discuss.leetcode.com/topic/37222/python-easy-iterative-and-recursive-solution

Python Easy Iterative and Recursive Solution

Recursive:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def kthSmallest(self, root, k):
self.k = k
self.res = None
self.helper(root)
return self.res

def helper(self, node):
if not node:
return
self.helper(node.left)
self.k -= 1
if self.k == 0:
self.res = node.val
return
self.helper(node.right)

Iterative:

1
2
3
4
5
6
7
8
9
10
11
def kthSmallest(root, k):
stack = []
while root or stack:
while root:
stack.append(root)
root = root.left
root = stack.pop()
k -= 1
if k == 0:
return root.val
root = root.right

https://discuss.leetcode.com/topic/17583/python-solution-using-iteration

Python Solution using iteration

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
# @param {TreeNode} root
# @param {integer} k
# @return {integer}
def kthSmallest(self, root, k):
i=0
stack=[]
node=root
while node or stack:
while node:
stack.append(node)
node=node.left
node=stack.pop()
i+=1
if i==k:
return node.val
node=node.right

For the follow up question, I think we could add a variable to the TreeNode to record the size of the left subtree. When insert or delete a node in the left subtree, we increase or decrease it by 1. So we could know whether the kth smallest element is in the left subtree or in the right subtree by compare the size with k.

谢谢你,可爱的朋友。