题解 | #判断一棵二叉树是否为搜索二叉树和完全二叉树#

1. 对于是否为BST，中序遍历递增就行（不能有等号）
2. 对于是否为Full，层序遍历，添加是否第一次遇到empty就行，如果第二次在有子树的时候，遇到了empty=true，那就是不满足。因为我们遍历时先左后右得。而满二叉树只允许最右边的有一个孩子的时候且必须在左边。

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */



class Solution {
public:

    TreeNode* pre = new TreeNode(-1000000);//作为假的第一个节点
    bool ISBST(TreeNode* root){

        if(!root) return true;// 结点为空返回true

        bool left = ISBST(root->left);// 判断左子树是否有序

        bool cur = pre->val < root ->val;// 判断当前节点是否有序
        pre = root;// 按中序遍历，记录前一个指针

        bool right = ISBST(root->right);// 判断右子树是否有序


        return left&&cur&&right;

    }


    //层序遍历
    bool ISFULL(TreeNode* root){

        if(!root) return true;

        bool isEmpty = false;//遇到得第一个空树。（如果是最后遇到的，没有一点问题，但是在中途遇到，就会有问题）

        queue<TreeNode*> q;
        q.push(root);

        while(!q.empty()){
            TreeNode* node= q.front();
            q.pop();

            if(node->left){
                if(isEmpty) return false; // 前面遇到空节点，此次还遇到了非空节点返回 false

                q.push(node->left);

            }else isEmpty = true;//此次遇到了空节点

            //如果左空右不空，也是false

            if(node->right){
                if(isEmpty) return false; // 前面遇到空节点，此次还遇到了非空节点返回 false

                q.push(node->right);

            }else isEmpty = true;//此次遇到了空节点


        }

        return true;

    }
    /**
     * 
     * @param root TreeNode类 the root
     * @return bool布尔型vector
     */
    vector<bool> judgeIt(TreeNode* root) {
        // write code here
        bool r1 = ISBST(root);
        bool r2 = ISFULL(root);

        return {r1,r2};
    }
};