LeetCode. 130(二叉搜索树中第k个最小的元素)

二叉搜索树又叫二叉排序树，

二叉查找树(Binary Search Tree)，(又:二叉搜索树，二叉排序树)它或者是一棵空树，或者是具有下列性质的二叉树: 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。

由此可知，对二叉搜索树进行中序排列，就是对二叉搜索树中所有的元素按照从小到大的顺序排列，那第K个最小的元素就是这个重排序列中的第k个元素。下面这个是上篇文章里一开始放的那个文章，为了方便，我再放过来。里面有关于中序遍历的相关内容。

二叉树遍历

写得时候要用到stack的常规操作，但是我不太熟悉，就找了篇博客，放在这里记录一下。

C++ STL stack 用法

代码如下：

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        stack<TreeNode* > temp;
        TreeNode *p=root;
        int count=0;
        while(p!=NULL||(temp.size()!=0)){
            while(p!=NULL){
                temp.push(p);
                p=p->left;
            }
            count++;
            if(count==k)
                return temp.top()->val;
            else {
                p=temp.top()->right;//如果这两句顺序颠倒，会有栈空时仍给p赋值，这样会报错。
                temp.pop();
                
            }
        }
        return -1;
    }
};