LeetCode OJ：Kth Smallest Element in a BST（二叉树中第k个最小的元素）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

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.

求二叉树中第k个最小的元素，中序遍历就可以了，具体代码和另一个Binary Tree Iterator差不多其实，这题由于把=写成了==调bug调了好久，细心细心啊啊啊。代码如下：

/**
* 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) {
stack<TreeNode *> s;
map<TreeNode *, bool> m;
if(root == NULL) return ;
s.push(root);
while(!s.empty()){
TreeNode * t = s.top();
if(t->left && !m[t->left]){
s.push(t->left);
m[t->left] = true;
continue;
}
s.pop();//这里pop
k--;
if(k == )
return t->val;
if(t->right && !m[t->right]){
s.push(t->right);
m[t->right] = true;
} }
}
};

java 版本的如下所示，同儿茶搜索树迭代器实际上是一样的：

public class Solution {
public int kthSmallest(TreeNode root, int k) {
int res;
HashMap<TreeNode, Integer> map = new HashMap<TreeNode, Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
if(root == null)
return 0;
stack.push(root);
while(!stack.isEmpty()){
TreeNode node = stack.peek();
while(node.left != null && !map.containsKey(node.left)){
stack.push(node.left);
map.put(node.left, 1);
node = node.left;
}
if(--k == 0)
return node.val;
stack.pop(); //这一步不要忘了
if(node.right != null && !map.containsKey(node.right)){
stack.push(node.right);
map.put(node.right, 1);
}
}
return 0;
}
}