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

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

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 the root
     * @return bool布尔型vector
     */
    bool ans = true;
    bool isCompleteTree(TreeNode* root) {
        queue<TreeNode*> qu;
        queue<int> order;
        vector<int> ans;
        qu.push(root);
        order.push(1);
        while(!qu.empty()){
            int size = qu.size();
            for(int i = 0;i < size;++i){
                TreeNode* cur = qu.front();
                int pos = order.front();
                ans.push_back(pos);
                order.pop();
                qu.pop();
                if(cur->left){
                    qu.push(cur->left);
                    order.push(pos * 2);
                }
                if(cur->right ){
                    qu.push(cur->right);
                    order.push(pos * 2 + 1);
                }
            }
        }
        int size = ans.size();
        for(int i = 1;i <= size;++i){
            if(ans[i - 1] == i);
            else return false;
        }
        return true;
    }
    void mid(TreeNode* root,int &pre){
        if(root == NULL)
            return;
        mid(root->left,pre);
        if(pre > root->val){
            ans = false;
            return;
        }
        else
            pre = root->val;
        mid(root->right,pre);
    }
    vector<bool> judgeIt(TreeNode* root) {
        // write code here
        if(root == NULL)
            return vector<bool> ({ans,true});
        int pre = 0;
        mid(root,pre);
        return vector<bool> ({ans,isCompleteTree(root)});
    }
};