编写一个算法，判断该树是否时BST（二叉排序树）
涉及知识点：
1. 二叉搜索树的中序遍历是有序的
2. 在算法中，如果需要逆序使用数组，此时可以用栈来做辅助

代码：

#include <bits/stdc++.h>
using namespace std;

stack<int> s;


//定义树节点结构体
struct TreeNode{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x),left(left), right(right) {}
};


void inorder(TreeNode* root){
    if(!root) return;
    if(root->left) inorder(root->left);
    s.push(root->val);
    if(root->right) inorder(root->right);

}


void isBst(TreeNode* root){

    inorder(root);
    int pre = s.top();
    s.pop();
    while(s.size()){
        int curr = s.top();
        s.pop();
        if(curr > pre){
            cout << "This is not bst!"<<endl;
            return;
        }
        pre = curr;
    }
    cout << "Yep! I think it's bst"<<endl;
}




int main()
{
    //创建一棵：1-7的BST
    TreeNode *root_BST = new TreeNode(4,
                                  new TreeNode(2,
                                               new TreeNode(1),
                                               new TreeNode(3)),
                                  new TreeNode(6,
                                               new TreeNode(5),
                                               new TreeNode(7)));

    //对照组：非BST
    TreeNode *root_NotBST = new TreeNode(2,
                                  new TreeNode(4,
                                               new TreeNode(1),
                                               new TreeNode(5)),
                                  new TreeNode(6,
                                               new TreeNode(3),
                                               new TreeNode(7)));

    isBst(root_BST);
    isBst(root_NotBST);


    return 0;
}

设计一个算法，找BST中的最大最小值。
方法一：
用双端队列来存中序遍历BST的结果，直接取头尾元素，即为最大最小值。

代码：和上面一题差不多，难点在于对双端队列的使用

deque<int> q;

在中序遍历中，不断将遍历到的元素加入到q

然后取出q的头尾即可,头是最小的，尾是最大的

int minnum = q.front();
int max = q.back();

方法二：
只要是树，就可以前、中、后序、层次遍历。任选一种遍历方式，将结果存在大根堆和小根堆中，取出即可。

priority_queue<int> maxi;
priority_queue<int,vetor<int>,greater> mini;

int mininum = mini.top();
int maxnum = maxi.top();

编写一个算法，查找在BST中是否存在该元素（二叉排序树）
要求：输入一个值，若存在于BST中，则输出SUCCESS!,不存在则输出NOT EXIST！
涉及知识点：
1. 递归遍历BST
2. 非递归遍历BST

递归版本

#include <bits/stdc++.h>
using namespace std;

stack<int> s;


//定义树节点结构体
struct TreeNode{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x),left(left), right(right) {}
};

bool isExist(TreeNode* root,int key){

    if(root == NULL ) return false;

    if(root->val == key) return true;
    else if(root->val < key) 
        return isExist(root->right,key);
    else if(root->val > key) 
        return isExist(root->left,key);

}


//      4
//   2     6
// 1   3  5  7 

int main()
{
    //创建一棵：1-7的BST
    TreeNode *root_BST = new TreeNode(4,
                                  new TreeNode(2,
                                               new TreeNode(1),
                                               new TreeNode(3)),
                                  new TreeNode(6,
                                               new TreeNode(5),
                                               new TreeNode(7)));


    if(isExist(root_BST,5)) cout << "Success!";
    else cout << "NOT Exist!";

    return 0;
}

非递归版本———基于层次遍历

bool isExist(TreeNode* root,int key){

    queue<TreeNode*> q; // 创建一个层次遍历必需的队列

    if(root == NULL ) return false;

    q.push(root);
    while(q.size()){

        auto p = q.front();
        q.pop();
        if(p->val == key) return true;
        if(p->left) q.push(p->left);
        if(p->right) q.push(p->right);
    }

    return false;
}