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

二叉搜索树的中序遍历是递增的。判断完全二叉树的方法：层次遍历，注意空结点可以入队列，当队列pop的过程中遇到第一个空结点时break，然后检查队列中的剩余元素，如果存在非空结点则不是完全二叉树。

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

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 the root
     * @return bool布尔型vector
     */
    void in_order(TreeNode* root,vector<int>& vec){
        if(root==nullptr) return;
        in_order(root->left,vec);
        vec.push_back(root->val);
        in_order(root->right,vec);
    }
    
    bool complete_tree(TreeNode* root){
        if(root==nullptr) return true;
        queue<TreeNode*> que{};
        que.push(root);
        while(!que.empty()){
            TreeNode* node=que.front();
            que.pop();
            if(node==nullptr) break;
            que.push(node->left);
            que.push(node->right);
        }
        while(!que.empty()){
            auto node=que.front();
            que.pop();
            if(node!=nullptr) return false;
        }
        return true;
    }
    
    vector<bool> judgeIt(TreeNode* root) {
        vector<int> in_vec{};
        in_order(root,in_vec);
        bool is_search=true;
        for(int i=1;i<in_vec.size();i++)
            if(in_vec[i]<in_vec[i-1]) is_search=false;
        
        bool is_complete=complete_tree(root);
        return {is_search,is_complete};
    }
};