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调了好久，细心细心啊啊啊。代码如下：

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     int kthSmallest(TreeNode* root, int k) {
13         stack<TreeNode *> s;
14         map<TreeNode *, bool> m;
15         if(root == NULL) return 0;
16         s.push(root);
17         while(!s.empty()){
18             TreeNode * t = s.top();
19             if(t->left && !m[t->left]){
20                 s.push(t->left);
21                 m[t->left] = true;
22                 continue;
23             }
24             s.pop();　　//这里pop
25             k--;
26             if(k == 0)
27                 return t->val;
28             if(t->right && !m[t->right]){
29                 s.push(t->right);
30                 m[t->right] = true;
31             }
32 
33         }
34     }
35 };

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

 1 public class Solution {
 2     public int kthSmallest(TreeNode root, int k) {
 3         int res;
 4         HashMap<TreeNode, Integer> map = new HashMap<TreeNode, Integer>();
 5         Stack<TreeNode> stack = new Stack<TreeNode>();
 6         if(root == null)
 7             return 0;
 8         stack.push(root);
 9         while(!stack.isEmpty()){
10             TreeNode node = stack.peek();
11             while(node.left != null && !map.containsKey(node.left)){
12                 stack.push(node.left);
13                 map.put(node.left, 1);
14                 node = node.left;
15             }
16             if(--k == 0)
17                 return node.val;
18             stack.pop(); //这一步不要忘了
19             if(node.right != null && !map.containsKey(node.right)){
20                 stack.push(node.right);
21                 map.put(node.right, 1);
22             }
23         }
24         return 0;
25     }
26 }